회전하는 절삭 공구

공작기계 기술은 계속 발전하고 있다. 최근 제안된 방식 하나는 공작물뿐 아니라 절삭 공구도 평행한 두 축을 중심으로 함께 회전하는 유연한 선반이다. 선반을 켜면 공작물과 절삭 공구가 같은 각속도로, 즉 같은 방향으로 같은 회전 속도로 돌기 시작한다. 절삭 공구와 만나는 순간 공작물에서 절삭 공구와 겹치는 부분이 깎여 나간다.

이 방식이 쓸모 있다는 것을 보이려고 이런 선반의 절삭 과정을 시뮬레이션한다.

공작물과 절삭 공구의 모양은 복잡할 수 있지만 두 회전축에 수직인 평면으로 자른 단면만 살펴보면 충분하다. 두 축에 수직인 평면에 $xy$ 좌표계를 잡고 공작물의 회전 중심을 원점 $(0, 0)$에, 절삭 공구의 회전 중심을 $(L, 0)$에 둔다. 공작물과 절삭 공구의 단면은 모두 다각형이고 볼록하지 않을 수도 있다.

이 단면이 두 조각 이상으로 나뉘어도 다른 단면에서는 공작물이 이어져 있으므로 잘린 조각이 떨어져 나가지는 않는다.

회전을 시작하기 전 공작물 내부에 완전히 들어 있는 격자점, 즉 내부에 있으면서 변 위에는 없고 $x$ 좌표와 $y$ 좌표가 모두 정수인 점을 관심점이라고 부른다.

공작물과 절삭 공구가 각각 360도를 한 바퀴 다 돌고 난 뒤 관심점이 몇 개 남는지 세어야 한다. 관심점이 남는다는 것은 그 점이 남은 공작물 내부에 완전히 들어 있다는 뜻이다. 주어진 공작물과 절삭 공구 배치에서 남는 관심점의 개수를 세는 프로그램을 작성하라.

그림 1. 첫 번째 예제의 공작물과 절삭 공구

그림 1(a)는 첫 번째 예제 입력의 공작물(검은 선)과 절삭 공구(파란 선)이다. 두 원은 각각의 회전 중심을 나타내고 붉은 십자 표시가 관심점이다. 그림 1(b)는 시계 방향으로 회전하는 도중의 모습이고 하늘색 부분이 깎여 나간 영역이다. 그림 1(c)는 그 결과다. 관심점 하나가 결과 도형의 변 위에 놓이는데 이 점은 세지 않는다. 남는 관심점은 여덟 개다.

입력은 테스트 케이스 하나로 이루어지고 형식은 다음과 같다.

M N L
xw1 yw1
.
.
.
xwM ywM
xc1 yc1
.
.
.
xcN ycN

첫 줄에 정수 세 개가 주어진다. $M$은 공작물의 꼭짓점 개수이고 $4 \le M \le 20$이다. $N$은 절삭 공구의 꼭짓점 개수이고 $4 \le N \le 20$이다. $L$은 절삭 공구의 회전 중심 위치를 정하며 $1 \le L \le 10000$이다.

이어지는 $M$개 줄에는 각각 정수 두 개가 있다. $i$번째 줄의 $xw_i$와 $yw_i$는 공작물의 $i$번째 꼭짓점이 $(xw_i, yw_i)$에 있다는 뜻이다. 꼭짓점은 반시계 방향으로 주어진다.

그다음 $N$개 줄은 같은 방식으로 절삭 공구의 꼭짓점을 주지만, 좌표는 회전 중심 $(L, 0)$에서 잰 상대 좌표다. 즉 절삭 공구의 $j$번째 꼭짓점은 $(L + xc_j, yc_j)$에 있다.

$1 \le i \le M$과 $1 \le j \le N$에 대해 $-10000 \le xw_i, yw_i, xc_j, yc_j \le 10000$이다.

회전을 시작하기 전 공작물과 절삭 공구의 모든 변은 $x$축이나 $y$축과 평행하다. 즉 $i' = (i \bmod M) + 1$이라 할 때 모든 $i$ ($1 \le i \le M$)에 대해 $xw_i = xw_{i'}$ 또는 $yw_i = yw_{i'}$이 성립한다. $x$축에 평행한 변과 $y$축에 평행한 변은 번갈아 나온다. 절삭 공구도 마찬가지다.

공작물의 단면은 단순 다각형이다. 즉 인접한 두 변을 빼면 어떤 두 변도 공통점을 갖지 않는다. 절삭 공구도 마찬가지다. 회전을 시작하기 전 공작물과 절삭 공구는 서로 닿지도 겹치지도 않는다.

$(0, 0)$이 항상 공작물 내부에 있는 것은 아니고 $(L, 0)$이 항상 절삭 공구 내부에 있는 것도 아니다.

남은 공작물 내부에 완전히 들어 있는 관심점의 개수를 출력한다.