24458번 - Prison Break

문제

억울하게 감옥에 갇힌 병준이는 볼록 $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$좌표는 정수이다.

출력

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

제한

힌트