32142번 - 서바이벌

경기과학고등학교 학생들은 수학여행에서 서바이벌 게임을 하게 되었다. 총 $N$명의 학생이 좌표평면 위에 모였으며, $i$번째 학생은 $(x_i, y_i)$에 위치해 있다. 이때 $x_i$와 $y_i$는 정수이며, 같은 점에 두 명 이상의 학생이 위치하는 경우는 없다.

학생들은 물리를 매우 잘하기에 적중률 100%의 사격 실력을 자랑하지만, 총의 성능은 좋지 않기에 자신과 가장 가까운 학생 1명에게만 총을 쏘려고 한다. 가장 가까운 학생이 여러 명 있을 경우 그중 가장 번호가 큰 학생에게 총을 쏘려고 한다.

이때, 각 학생이 쏜 총알의 경로는 두 학생을 잇는 선분으로 생각할 수 있다. 그렇다면, 몇 명의 학생들이 총을 쏘아 총알의 경로로 단순다각형을 이룰 수 있다.

엄밀히 하여, $M$명의 학생 $s_1, s_2, ..., s_M$번 학생이 단순다각형을 이룬다는 것은 다음과 같다. (이때, $M \geq 3$인 경우만 단순다각형을 이룰 수 있다.)

• $s_i$번 학생은 $s_{i+1}$번 학생에게 총을 쏜다($1 \leq i \leq M-1$). 또, $s_M$번 학생은 $s_1$번 학생에게 총을 쏜다.
• 각 학생이 쏜 $M$개의 총알의 경로만 고려할 때, 각 총알의 경로는 양 끝점 이외의 점에서 다른 경로와 만나지 않는다.

경기과학고등학교 학생들의 수와 각 학생들의 위치가 번호 순서대로 주어질 때, 총알의 경로가 만드는 단순다각형 중 변의 개수가 가장 많은 것을 찾아 그 변의 개수를 출력하여라. 만약 단순다각형이 1개도 만들어지지 않는다면 $-1$을 출력하여라.

첫 번째 줄에 학생의 수 $N$이 주어진다.

그 다음 $N$개의 줄 중 $i$번째 줄에 $i$번 학생의 좌표 $x_i$, $y_i$가 공백으로 구분되어 주어진다.

첫 번째 줄에 총알의 경로가 만드는 변의 개수가 가장 많은 단순다각형의 변의 개수를 출력한다.

만약 단순다각형이 1개도 만들어지지 않는다면 $-1$을 출력한다.

• $3 \leq N \leq 300\,000$
• $-10^9 \leq x_i, y_i \leq 10^9$ ($1 \leq i \leq N$)
• $i \neq j$이면 $(x_i,y_i) \neq (x_j,y_j)$

점이나 선분은 단순다각형이 아니다.

학생들은 유클리드 평면상에 있으며, 두 점 $(x_i,y_i)$와 $(x_j,y_j)$ 사이의 거리는 $\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$로 정의된다.