풍차 축 전환
시간 제한10초메모리 제한512 MB
세 점이 한 직선 위에 있지 않은 n개의 점이 주어질 때, 직선을 한 바퀴 돌리는 동안 한 점이 피벗이 되는 최대 횟수를 구합니다.
문제
평면 위의 점 집합 를 생각합니다. 어떤 세 점도 한 직선 위에 있지 않습니다. 다음 절차로 풍차를 만듭니다.
- 점 와 시작 방향을 고릅니다. 그 방향으로 를 지나는 직선을 그었을 때 의 다른 점과 교차하지 않아야 합니다. 그을 것은 직선이며, 반직선이 아닙니다.
- 직선을 를 축으로 풍차처럼 시계 방향으로 회전시킵니다. 직선이 다른 점 와 만날 때까지 돌립니다. 점 를 새 축으로 지정하고 회전을 계속합니다. 이를 점 를 승격시킨다고 합니다.
- 직선이 360° 회전하여 처음 방향으로 돌아올 때까지 이 과정을 계속합니다. (360° 회전 후 직선이 원래 위치로 돌아온다는 것은 증명할 수 있습니다.)
이 과정에서 어떤 점은 여러 번 축이 될 수 있습니다. 가능한 모든 시작 축과 시작 방향을 고려할 때, 풍차가 한 번 360° 회전하는 동안 한 점이 승격되는 횟수의 최댓값을 구하세요. 첫 번째 점은 축이지만, 시작할 때 승격된 것으로 세지 않습니다.
입력
입력의 첫 줄에 정수 ()이 주어집니다. 이는 점 의 개수입니다.
이어지는 개의 줄에는 공백으로 구분된 정수 와 ()가 주어집니다. 이것이 점들입니다. 각 점은 서로 다르며, 어떤 세 점도 한 직선 위에 있지 않습니다.
출력
한 번의 360° 회전과 임의의 시작점을 고려할 때, 어떤 점 가 승격되는 횟수의 최댓값을 정수 하나로 출력하세요.