10213 - How Many Pieces of Land?
Count the maximum number of regions as defined by the problem statement.
Any proper strategy for choosing the points should ensure that no three lines intersect. Consider a line that goes through a region of the ellipse without intersecting any other line. It adds 1 to the number of regions that were already defined. Now, consider every quadrilateral formed by the points. These quadrilaterals each have 1 internal intersection, which also adds 1 to the count of the number of regions.
Therefore, in total the number of regions is: 1 + number of lines + number of quadrilaterals = 1 + n choose 2 + n choose 4
The example output makes it look like the closed formula for the sequence is , but for the answer is 31. Also, the input can be as large as . Will BigNum be required to calculate the answer?
This is actually the same for a circle as well, and posed for a circle this problem is known as Moser's Circle Problem.
6 1 2 3 4 5 6
1 2 4 8 16 31