Problem K
Kingdom of Cats

You probably still remember the problem Kingdom of Kittens from The $2\, 018$ ICPC Asia Hanoi Regional Contest. It has been two years since then, the kingdom has since evolved into Kingdom of Cats, with even more challenging problems.

As their kingdom grows, the cats need to set a new border for their kingdom. They have found $n$ beautiful bushes. They decided to use these bushes to mark the border of their kingdom.

Unfortunately, cats are not so good at geometry, so they want the border to be a polygon with exactly four sides. Additionally, to avoid confusion, for each pair of points inside the polygon, all points on the segment connecting the pair must also lie inside the polygon. In other words, the border must be a convex polygon. As their plan is still under discussion, the cats want you to tell them how many ways to choose the border satisfying all their needs.

More formally, given $n$ points on a Cartesian coordinate plane, you should count the number of convex polygons with positive area whose all $4$ vertices are amongst the $n$ points.


The input contains multiple test cases. Each test case is descried as below:

  • The first line contains a single positive integer $n$ — the number of points $(1 \le n \le 50)$. The sum of $n$ in all test cases does not exceed $500$.

  • In the next $n$ lines, the $i$-th line contains two integers $x_ i$ and $y_ i$ — the coordinates of the $i$-th point $(-10^9 \le x_ i, y_ i \le 10^9)$. It is guaranteed that no two points have the same coordinates.

The input is terminated with a line containing a single $0$.


For each test case, print a single line containing the number of different convex polygons satisfying the given conditions.

Explanation of the first sample

\includegraphics[width=.9\textwidth ]{images/all.png}
Sample Input 1 Sample Output 1
4 1
3 1
2 1
1 1
1 2
1 3
1 4
0 0
0 2
2 0
2 2

Please log in to submit a solution to this problem

Log in