27319번 - 치노의 라떼 아트 (Hard)

치노는 하트 모양의 라떼 아트를 만드는 연습을 하고 있다. 치노가 수없이 연습한 흔적을 우연히 보게 된 코코아는 그 중에서 하트 모양의 라떼 아트가 얼마나 있는지 궁금해졌다. 코코아를 위해 라떼 아트가 하트 모양인지 판별하는 프로그램을 만들어주자.

이 문제에서 치노의 라떼 아트는 하나의 단순 다각형이다.

또한 하트 모양의 정의는 다음과 같다. 다각형의 꼭지점 $A$, $B$가 존재하여 다음의 조건을 모두 만족하는 다각형을 하트 모양으로 정의한다.

• $A$의 내각은 $180$도보다 작고, $B$의 내각은 $180$도보다 크다.
• 주어진 다각형이 직선 $AB$에 대해 대칭이다.
• 주어진 다각형을 선분 $AB$로 나누었을 때 만들어지는 두 부분은 모두 볼록 다각형이다.

첫 번째 줄에 다각형의 꼭짓점의 개수 $N$이 주어진다. ($3 \le N \le 100\,000$)

다음 $N$개의 줄에 각 꼭짓점의 $x$좌표, $y$좌표가 공백으로 구분되어 주어진다. ($-10^9 \le x,y \le 10^9$, $x$, $y$는 정수)

꼭짓점들은 임의의 점에서 시작해서 시계 방향으로 주어진다.

주어진 다각형에 내각이 정확히 $180$도인 꼭짓점은 존재하지 않는다.

주어진 다각형이 하트 모양이면 1, 아니면 0을 출력한다.