# UVa 10213

## Contents

## 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