평행선

시간 제한10초메모리 제한512 MB

요약

서로 다른 점을 최대 16개 주면, 모든 점을 짝지었을 때 그은 선분들 중 서로 평행한 쌍의 수가 최대가 되도록 만든다.

난이도: 어려움10점 중 8점
유형: 비트 연산, 동적 계획법, 기하, 조합론
정답자: 아직 제출이 없습니다

문제

평면 위에 서로 다른 점이 짝수 개 주어진다. 모든 점을 두 개씩 짝지어 나누는 방법을 생각하자. 각 점은 정확히 다른 한 점과만 짝을 이루며, 이런 짝짓기를 모두 살펴본다.

짝지은 두 점을 선분으로 이으면 어떤 선분은 다른 선분과 평행해진다. 가능한 모든 짝짓기 중에서 평행한 선분 쌍의 개수가 최대인 값을 구하라.

네 점 $(0, 0)$ , $(1, 1)$ , $(0, 2)$ , $(2, 4)$ 가 주어진 경우 짝짓는 방법은 그림 B.1처럼 세 가지다. 평행한 선분 쌍의 개수는 왼쪽부터 0, 0, 1이므로 최댓값은 1이다.

그림 B.1. 네 점을 짝짓는 세 가지 방법

점이 여덟 개인 경우에는 그림 B.2처럼 짝지을 수 있다. 이렇게 짝지으면 선분 네 개가 모두 서로 평행하다. 즉 $(L_1, L_2)$ , $(L_1, L_3)$ , $(L_1, L_4)$ , $(L_2, L_3)$ , $(L_2, L_4)$ , $(L_3, L_4)$ 여섯 쌍이 모두 평행하므로 최댓값은 6이다.

그림 B.2. 여덟 점에서 평행한 선분 쌍을 최대로 만든 짝짓기

입력

입력은 다음 형식의 테스트 케이스 하나로 이루어진다.

m
x1 y1
.
.
.
xm ym

첫 줄에 점의 개수인 짝수 $m$ 이 주어진다 ( $2 \le m \le 16$ ). 이어지는 $m$ 개 줄 중 $i$ 번째 줄에는 $i$ 번째 점의 $x$ 좌표와 $y$ 좌표를 나타내는 정수 $x_i$ 와 $y_i$ 가 주어진다 ( $-1000 \le x_i \le 1000$ , $-1000 \le y_i \le 1000$ ).

모든 점의 위치는 서로 다르다. 즉 $i \ne j$ 이면 $x_i \ne x_j$ 또는 $y_i \ne y_j$ 가 성립한다. 또한 한 직선 위에 점이 세 개 이상 놓이는 경우는 없다.

출력

평행한 선분 쌍의 최대 개수를 한 줄에 출력한다.

예제5

예제 1
입력
```
4
0 0
1 1
0 2
2 4
```
예상 출력
```
1
```
예제 2
입력
```
8
0 0
0 5
2 2
2 7
3 -2
5 0
4 -2
8 2
```
예상 출력
```
6
```
예제 3
입력
```
6
0 0
0 5
3 -2
3 5
5 0
5 7
```
예상 출력
```
3
```
예제 4
입력
```
2
-1000 1000
1000 -1000
```
예상 출력
```
0
```

예제 5

입력

예상 출력