경계선의 꼭짓점 개수

시간 제한2초메모리 제한128 MB

요약

자기 교차하는 닫힌 폴리라인이 주어질 때, 모든 유계 영역을 감싸는 내부의 경계 폴리라인 꼭짓점 개수를 구한다.

난이도: 어려움10점 중 9점
유형: 기하, 구현, 시뮬레이션, 정렬
정답자: 아직 제출이 없습니다

문제

닫힌 꺾은선(자기 자신과 교차할 수도 있습니다)은 평면을 여러 개의 영역으로 나눕니다. 이 영역들 중 정확히 하나만 무한히 뻗어 있으며, 이 영역을 꺾은선의 외부라고 합니다. 나머지 유한한 영역들과 꺾은선 자체를 모두 합친 것을 꺾은선의 내부라고 합니다(아래 그림에서 음영으로 표시된 부분). 내부의 경계선(그림에서 굵은 선)은 그 자체로 또 하나의 꺾은선이며, 원래 꺾은선과 정확히 같은 내부를 둘러쌉니다.

경계선이 (시작점을 제외하면) 유일하게 정해지도록, 경계선은 다음 조건을 모두 만족합니다.

자기 자신과 교차하지 않습니다. 단, 한 점에서 맞닿을 수는 있습니다.
이웃한 두 꼭짓점이 같은 위치에 있지 않습니다.
이웃한 두 변이 일직선을 이루지 않습니다.
경계선을 따라 진행할 때, 내부는 항상 진행 방향의 왼쪽에 있습니다.

주어진 꺾은선에 대해, 이 경계선이 몇 개의 꼭짓점으로 이루어져 있는지 구하세요.

입력

첫째 줄에 원래 꺾은선의 꼭짓점 개수 $n$ ( $3 \le n \le 100$ )이 주어집니다. 다음 $n$ 개의 줄에는 각 꼭짓점의 좌표를 나타내는 두 정수 $x_i$ 와 $y_i$ ( $0 \le x_i, y_i \le 100$ )가 주어집니다. 모든 꼭짓점은 서로 다르고, 어떤 꼭짓점도 다른 두 꼭짓점을 잇는 변의 내부에 놓이지 않으며, 이웃한 두 변은 일직선을 이루지 않습니다.

출력

내부 경계선의 꼭짓점 개수 $m$ 을 정수 하나로 출력하세요.

예제4

예제 1

입력

예상 출력

예제 2
입력
```
3
0 0
10 0
0 10
```
예상 출력
```
3
```
예제 3
입력
```
4
0 0
10 0
10 10
0 10
```
예상 출력
```
4
```
예제 4
입력
```
4
0 0
4 4
4 0
0 4
```
예상 출력
```
6
```