만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

풍차 축 전환

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

요약
세 점이 한 직선 위에 있지 않은 n개의 점이 주어질 때, 직선을 한 바퀴 돌리는 동안 한 점이 피벗이 되는 최대 횟수를 구합니다.
난이도

보통10점 중 7점

유형
기하, 정렬
정답자
아직 제출이 없습니다

문제

평면 위의 점 집합 PP를 생각합니다. 어떤 세 점도 한 직선 위에 있지 않습니다. 다음 절차로 풍차를 만듭니다.

  • 점 p∈Pp \in P와 시작 방향을 고릅니다. 그 방향으로 pp를 지나는 직선을 그었을 때 PP의 다른 점과 교차하지 않아야 합니다. 그을 것은 직선이며, 반직선이 아닙니다.
  • 직선을 pp를 축으로 풍차처럼 시계 방향으로 회전시킵니다. 직선이 다른 점 q∈Pq \in P와 만날 때까지 돌립니다. 점 qq를 새 축으로 지정하고 회전을 계속합니다. 이를 점 qq를 승격시킨다고 합니다.
  • 직선이 360° 회전하여 처음 방향으로 돌아올 때까지 이 과정을 계속합니다. (360° 회전 후 직선이 원래 위치로 돌아온다는 것은 증명할 수 있습니다.)

이 과정에서 어떤 점은 여러 번 축이 될 수 있습니다. 가능한 모든 시작 축과 시작 방향을 고려할 때, 풍차가 한 번 360° 회전하는 동안 한 점이 승격되는 횟수의 최댓값을 구하세요. 첫 번째 점은 축이지만, 시작할 때 승격된 것으로 세지 않습니다.

입력

입력의 첫 줄에 정수 nn (2≤n≤20002 \le n \le 2000)이 주어집니다. 이는 점 p∈Pp \in P의 개수입니다.

이어지는 nn개의 줄에는 공백으로 구분된 정수 xx와 yy (−105≤x,y≤105-10^5 \le x, y \le 10^5)가 주어집니다. 이것이 점들입니다. 각 점은 서로 다르며, 어떤 세 점도 한 직선 위에 있지 않습니다.

출력

한 번의 360° 회전과 임의의 시작점을 고려할 때, 어떤 점 p∈Pp \in P가 승격되는 횟수의 최댓값을 정수 하나로 출력하세요.

예제2

  1. 예제 1

    입력
    3
    -1 0
    1 0
    0 2
    
    예상 출력
    2
    
  2. 예제 2

    입력
    6
    0 0
    5 0
    0 5
    5 5
    1 2
    4 2
    
    예상 출력
    3