33519번 - Andrew the Diver

문제

수중 동굴에는 다양한 생물이 서식하고 있다. 수중생물학자 Andrew는 동굴의 생태에 관심이 있어 수중 동굴 속으로 직접 들어가 동굴의 생태에 대해 조사하고자 한다.

Andrew는 조사하려는 수중 동굴은 2ドル$차원 지도로 나타낼 수 있으며, 동굴에는 $-y$ 방향으로 햇빛이 비치고 있다. 그러므로 동굴 입구에서 $-y$ 방향을 바라봤을 때 직접 보이는 영역은 밝은 영역이다. 반면에 직접 보이지 않는 영역은 햇빛이 닿지 않아 어두운 영역이다. 어두운 영역에 있는 임의의 두 지점을 선택하여 벽을 통과하지 않도록 연결하였을 때 어떤 방법으로 연결하더라도 밝은 영역을 반드시 지나게 된다면 두 지점은 서로 다른 영역에 속한다. 반대로 밝은 영역을 지나지 않게 두 지점을 연결할 수 있다면 두 지점은 같은 영역에 속한다. 또한 어두운 영역은 변들이 꼭짓점에서만 만나는 단순다각형이어야 한다.

수중 동굴에 빛이 수직 아래로 내려올 때, 동굴 형태에 의해 빛이 닿지 않는 영역을 주변보다 어둡게 표시한 모습

예를 들어 위 그림에서 $A$ 지점과 $B$ 지점은 어떻게 연결하더라도 밝은 영역을 지나게 되므로 서로 다른 영역에 속하는 지점이지만, $A$ 지점과 $C$ 지점은 같은 영역에 속한다.

동굴 지도가 주어질 때, 어두운 영역의 수를 출력하시오.

입력

첫 번째 줄에는 수중 동굴의 꼭짓점의 수 $N$이 주어진다. $(3 \le N \le 100,000円)$

다음 $N$개의 줄에 걸쳐 수중 동굴의 꼭짓점의 좌표 $(x_i, y_i)$가 순서대로 주어진다. 이웃한 두 점을 연결한 선분은 수중 동굴의 벽을 이룬다. $(1 \le i \le N;$ 0ドル \le x_i, y_i \le 10^9;$ $x_1 < x_N;$ 1ドル < j < N;$ $y_j < y_1=y_N)$

수중 동굴의 벽을 이루는 두 선분은 연속하는 두 선분의 교점을 제외하고는 교차하지 않는다. 연속된 세 동굴의 꼭짓점이 한 직선 위에 존재하지 않는다.

입력으로 주어지는 모든 수는 정수이다.

출력

수중 동굴의 어두운 영역의 수를 출력한다.

제한

노트