# UVa 10213

## Summary

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

## Explanation

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

The example output makes it look like the closed formula for the sequence is ${\displaystyle 2^{n-1}}$, but for ${\displaystyle n=6}$ the answer is 31. Also, the input can be as large as ${\displaystyle 2^{31}-1}$. Will BigNum be required to calculate the answer?

## Notes

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