Description

To enjoy the most traditional and pure cuisine, Uncle Fang decides to cultivate a vegetable garden. There is a piece of open land with $n$ planned spots where he intends to plant vegetables.

The freshest vegetables must be irrigated with the sweetest well water, so Uncle Fang will dig two wells, called well A and well B. The questions are: where to dig the wells, and which vegetables should each well irrigate? Since Uncle Fang is not good at calculations, he proposes the following principles and asks you to find all schemes that satisfy them:

1. Each well must be placed at the centroid of the vegetables it irrigates. That is, if a well’s coordinates are $(X, Y)$, then $X$ (respectively $Y$) equals the average of the $x$ (respectively $y$) coordinates of all vegetables it irrigates.
2. All vegetables must be irrigated.
3. Each of the two wells must irrigate at least one vegetable.
4. Any vegetable that is closer to well A must be irrigated by well A; any vegetable that is closer to well B must be irrigated by well B. When the distances are equal, either well may irrigate that vegetable.

Of course, the two wells cannot be at the same position, and no two vegetables are planted at the same position.

We define the well that irrigates vegetable $1$ as well A. Two schemes are considered different if and only if the set of vegetables irrigated by well A is different.

Input Format

The first line contains an integer $n$, the number of vegetables.
The next $n$ lines each contain two integers $x_i$, $y_i$, representing the coordinates of the $i$-th vegetable.

Output Format

Output a single integer: the number of feasible schemes.

3
3 4
1 1
5 1

3

Hint

Constraints: $1 \le n \le 60$, $0 \le x_i, y_i \le 60$.

Translated by ChatGPT 5