Description

There are some points on a plane. You can connect two points with a straight segment. How many ways are there to connect these points in sequence to form a closed polygonal chain such that no two segments intersect (except at shared endpoints)?

Obviously, with three points there is only one way. With four points there are at most $3$ ways. Write a program to compute the total number of ways.

Input Format

Each line contains the coordinates of one point: two integers separated by a single space. The last line is the origin $(0, 0)$. No three points are collinear.

Output Format

Output the total number of valid ways.

100 -10
-200 0
45 7
0 0

3

Hint

At most $10$ points.

• Only a tour that starts at some point, visits all points, and returns to the starting point will be counted.
• Two solutions are different if and only if the resulting simple polygon is different.

Translated by ChatGPT 5