마법 장벽

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

요약

세 점이 한 직선 위에 없는 N개의 점이 주어질 때, 두 점을 잇는 선분 하나가 다른 선분 중 몇 개와 교차하는지 그 최댓값을 구합니다.

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

문제

ICPC 왕국 곳곳에 $1$ 부터 $N$ 까지 번호가 붙은 권력 원천 $N$ 개가 흩어져 있다. 원천 $i$ 는 2차원 직교 좌표계의 $(X_i, Y_i)$ 위치에 있다. 어떤 세 원천도 일직선 위에 놓이지 않는다.

서로 다른 원천 $i$ , $j$ ( $1 \le i < j \le N$ ) 쌍마다 $(X_i, Y_i)$ 에서 $(X_j, Y_j)$ 까지 잇는 선분 모양의 마법 장벽이 생긴다.

이상한 현상이 관찰되었다. 서로 다른 두 마법 장벽이 교차하면 두 장벽이 모두 강해진다. 장벽 $b$ 의 세기는 $b$ 와 교차하는 $b$ 이외의 마법 장벽의 개수이다. 서로 다른 두 마법 장벽이 교차한다는 것은, 두 장벽이 모두 지나는 점 $(x, y)$ 가 정확히 하나 있고 그 점에 $N$ 개의 원천 중 어느 것도 놓여 있지 않은 경우이다.

ICPC 왕국의 마법 장벽 중 가장 강한 장벽의 세기를 구하라.

입력

첫 줄에 원천의 개수 정수 $N$ ( $2 \le N \le 1000$ )이 주어진다. 이어지는 $N$ 개의 줄에는 각각 정수 $X_i$ , $Y_i$ ( $-10^9 \le X_i, Y_i \le 10^9$ )가 주어지며, 이는 원천 $i$ 의 위치이다. 모든 위치는 서로 다르고, 어떤 세 원천도 일직선 위에 있지 않다.

출력

가장 강한 마법 장벽의 세기를 한 줄에 정수로 출력한다.

예제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
```