Magical Barrier

시간 제한2초메모리 제한1024 MB

요약

세 점이 일직선 위에 있지 않은 N개의 점이 주어질 때, 각 쌍이 선분을 이루며 한 선분과 교차하는 다른 선분 수의 최댓값을 구한다.

난이도: 보통10점 중 6점
유형: 기하, 정렬, 완전 탐색
정답자: 아직 제출이 없습니다

문제

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 ≤ i < j ≤ 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 ≤ N ≤ 1000$ ) representing the number of power sources. Each of the next $N$ lines contains $2$ integers $X\_i$ $Y\_i$ ( $-10^9 ≤ X\_i , Y\_i ≤ 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.

예제4

예제 1
입력
```
6
0 0
0 6
6 0
6 6
1 4
1 2
```
예상 출력
```
3
```
예제 2
입력
```
2
0 0
0 1
```
예상 출력
```
0
```
예제 3
입력
```
4
-3 0
3 0
0 3
0 1
```
예상 출력
```
0
```
예제 4
입력
```
4
0 0
0 1
1 0
1 1
```
예상 출력
```
1
```