UVa 10213

From Algorithmist
Jump to navigation Jump to search

10213 - How Many Pieces of Land?[edit]

Summary[edit]

Count the maximum number of regions as defined by the problem statement.

Explanation[edit]

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

Gotchas[edit]

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?

Notes[edit]

This is actually the same for a circle as well, and posed for a circle this problem is known as Moser's Circle Problem.

Input[edit]

6
1
2
3
4
5
6

Output[edit]

1
2
4
8
16
31