감옥 탈출

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

요약

볼록 다각형과 내부 또는 외부에 있는 점들이 주어질 때, 외부 경비가 볼 수 없는 변의 개수를 센다. 경비가 변을 본다는 것은 그 변이 경비의 시야에 들어온다는 뜻이다.

난이도: 어려움10점 중 8점
유형: 기하, 정렬, 투 포인터, 이분 탐색
정답자: 아직 제출이 없습니다

문제

억울하게 감옥에 갇힌 병준이는 볼록 $N$ -각형 모양의 감옥을 탈출하려고 한다. 감옥의 안팎에는 총 $M$ 명의 간수가 감옥을 지키고 있다.

병준이는 감옥 안쪽의 모든 간수는 매수에 성공했지만, 감옥 밖의 간수는 매수에 실패했다. 그래서 감시가 허술한 감옥의 벽을 찾아 탈옥하려고 한다.

위 그림을 예로 들어 보자. 감옥은 볼록팔각형 모양이고, 감옥의 벽은 팔각형의 변, 감옥의 기둥은 팔각형의 꼭짓점이다. $\texttt{A},\ \texttt{B},\ \texttt{C}$ 를 간수라고 하자. $\texttt{A},\ \texttt{B}$ 가 감시하는 감옥의 벽은 빨간색으로 표시된 변이다. ( $\texttt{B}$ 를 보면, 간수는 자신과 일직선을 이루는 벽을 감시할 수 없음을 알 수 있다.) $\texttt{C}$ 는 매수된 간수이므로 무시할 수 있다. $\texttt{A},\ \texttt{B}$ 가 감시하지 못하는 벽은 $4$ 개(검은색)이므로 감시가 허술한 감옥의 벽은 $4$ 개다.

병준이의 탈출을 위해 감시가 허술한 벽의 개수를 구하는 프로그램을 작성하시오.

단, 감옥을 이루는 임의의 세 기둥은 일직선상에 위치하지 않고 감옥의 벽과 기둥에는 간수가 존재하지 않는다. 또한 벽의 두께는 무시한다.

두 명 이상의 간수가 같은 위치에 있을 수도 있다.

입력

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

두 번째 줄부터 $N$ 줄에 걸쳐 감옥의 기둥의 좌표 $(x_i,\ y_i)$ 가 반시계방향으로 주어진다. ( $\vert x_i\vert ,\ \vert y_i \vert \le 10^8$ )

$N+2$ 번째 줄에는 간수의 수 $M(1 \le M \le 100\,000)$ 가 주어진다.

$N+3$ 번째 줄부터 $M$ 줄에 걸쳐 간수의 좌표 $(x_i,\ y_i)$ 가 주어진다. ( $\vert x_i\vert ,\ \vert y_i \vert \le 2 \times 10^8$ )

모든 $x,\ y$ 좌표는 정수이다.

출력

첫 번째 줄에 감시가 허술한 감옥의 벽의 개수를 출력한다.

예제2

예제 1
입력
```
4
0 0
1 0
1 1
0 1
3
-1 -1
3 -1
1 5
```
예상 출력
```
0
```
예제 2
입력
```
4
0 0
1 0
1 1
0 1
3
-1 1
2 1
0 -1
```
예상 출력
```
1
```