题目描述

There are $N$ power sources, numbered from 1 to $N$, scattered around the ICPC Kingdom. Power source $i$ is uniquely located at coordinate $(X_i, Y_i)$ in a 2D Cartesian plane such that there are no three power sources located in a straight line.

For each pair of distinct power sources $i$ and $j$ that satisfies $1 \leq i < j \leq N$, a magical barrier forms as a line segment that spans from $(X_i, Y_i)$ to $(X_j, Y_j)$.

You noticed a strange phenomenon. When two distinct magical barriers are intersecting, then both magical barriers are somewhat strengthened. To simplify things, you define the strength of a magical barrier $b$ as the number of magical barriers other than $b$ that intersects with $b$. Two distinct magical barriers are intersecting if and only if there exists exactly one point $(x, y)$ that lies on both magical barriers while none of the $N$ power sources are located at $(x, y)$.

You want to find the strength of the strongest magical barrier in the ICPC Kingdom.

输入格式

Input begins with an integer $N$ ($2 \leq N \leq 1000$) representing the number of power sources. Each of the next $N$ lines contains 2 integers $X_i$ $Y_i$ ($-10^9 \leq X_i, Y_i \leq 10^9$) representing the location of power source $i$. It is guaranteed that the location of each power source is unique, and there are no three power sources located in a straight line.

输出格式

Output an integer in a single line representing the strength of the strongest magical barrier.

6
0 0
0 6
6 0
6 6
1 4
1 2

3

2
0 0
0 1

0

4
-3 0
3 0
0 3
0 1

0

4
0 0
0 1
1 0
1 1

1

提示

Explanation for the sample input/output #1

Let $\langle i, j \rangle$ be the magical barrier that spans from power source $i$ to power source $j$.

One of the strongest magical barriers is $\langle 1, 4 \rangle$ with a strength of $3$. The $3$ magical barriers that intersect with $\langle 1, 4 \rangle$ are $\langle 2, 3 \rangle$, $\langle 3, 6 \rangle$, and $\langle 3, 5 \rangle$. Note that the magical barrier $\langle 2, 3 \rangle$ also has a strength of $3$.

Explanation for the sample input/output #2

The only magical barrier is $\langle 1, 2 \rangle$ with a strength of $0$.

Explanation for the sample input/output #3

All magical barriers have a strength of $0$.

Explanation for the sample input/output #4

The strongest magical barrier is either $\langle 1, 4 \rangle$ or $\langle 2, 3 \rangle$, which intersects each other at $(0.5, 0.5)$.