보이 스카우트

시간 제한1초메모리 제한128 MB

요약

일반 위치에 있는 N개 점이 주어질 때, 매 단계마다 왼쪽으로만 엄격하게 회전하며 돌아오는 가장 긴 닫힌 경로의 방문 점 수를 구한다.

난이도: 보통10점 중 7점
유형: 기하, 동적 계획법, 정렬
정답자: 아직 제출이 없습니다

문제

보이 스카우트에서는 매년 올림픽을 연다. 올해는 새로운 게임이 추가된다.

경기장에는 $N$ 개의 나무가 있고, 각 나무의 위치는 평면 위의 한 점으로 주어진다. 한 팀은 나무 하나를 골라 그 나무에서 출발한다. 한 나무에서 다른 나무로 이동할 때는 항상 직선으로 이동한다. 출발한 나무로 다시 돌아올 때까지 방문한 서로 다른 나무의 개수가 그 팀의 점수가 된다.

단, 규칙이 하나 있다. 이동할 때마다 반드시 반시계 방향으로 방향을 틀어야 한다. 즉, 어떤 나무에 도착한 뒤 다음 나무로 향할 때에는 진행 방향을 왼쪽으로 $0$ 도 초과 $180$ 도 미만 만큼만 회전할 수 있다. (직진하거나, 오른쪽으로 돌거나, 정확히 반대 방향으로 되돌아가는 것은 허용되지 않는다.)

이 규칙을 지키며 출발한 나무로 되돌아오는 경로들 중에서, 방문한 나무의 수(점수)를 최대로 만들고 싶다. 나무들의 위치가 주어질 때 얻을 수 있는 최대 점수를 구하여라.

입력

첫째 줄에 나무의 수 $N$ ( $3 \le N \le 100$ )이 주어진다.

다음 $N$ 개의 줄에는 각 나무의 좌표가 주어진다. $i$ 번째 줄에는 두 실수 $x$ , $y$ ( $-10^6 \le x, y \le 10^6$ )가 공백으로 구분되어 주어진다. 각 좌표는 소수점 아래 둘째 자리까지 주어진다.

한 직선 위에 서로 다른 세 개 이상의 나무가 놓이는 경우는 없다.

출력

얻을 수 있는 최대 점수를 첫째 줄에 출력한다.

예제3

예제 1
입력
```
5
0 0
1.5 -0.25
0 -1
-1 0.5
0.5 1
```
예상 출력
```
4
```
예제 2
입력
```
3
0 0
10 0
0 10
```
예상 출력
```
3
```
예제 3
입력
```
4
0 0
4 0
4 4
0 4
```
예상 출력
```
4
```