32987번 - 촛불과 그림자 2

문제

꼭짓점이 $(A_1, B_1), (A_2, B_2), \cdots, (A_N, B_N)$인 빨간색 볼록 $N$각형 벽과, 꼭짓점이 $(C_1, D_1), (C_2, D_2), \cdots, (C_M, D_M)$인 파란색 볼록 $M$각형 벽이 있다. 여기서 재미있는 점은, 아래 그림과 같이 파란색 볼록 다각형이 빨간색 볼록 다각형에 완전하게 포함된다. 구체적으로, 파란색 다각형의 모든 꼭짓점과 변은 모두 빨간색 다각형 내부 영역에 위치해 있으며 빨간색 다각형의 꼭짓점이나 변과 접해 있지도 않다.

[그림 1] 파란색 다각형을 포함하는 빨간색 다각형

벽과 벽 사이의 영역, 곧 빨간색 볼록 다각형 내부이면서 파란색 볼록 다각형 외부인 영역을 $S$라고 하자. 아래 그림과 같이, 영역 $S$의 한 점에 촛불을 설치하면 노란색 영역이 밝아지고, 회색 영역에는 그림자가 생긴다. $S$는 빨간색 및 파란색 볼록 다각형의 경계도 포함한다.

[그림 2] 밝혀진 영역과 그림자 영역

두 벽 사이 공간에 갇혀 있는 은호는 갑작스레 귀신이 출몰할까 봐 두려움에 떨고 있다. 이에 $S$ 내부에 촛불 몇 개를 두어 영역 $S$를 전부 밝히려고 한다. $S$ 내부를 한 틈도 남김없이 모두 밝히기 위해 필요한 촛불의 최소 개수를 구하여라.

입력

첫 번째 줄에 빨간색 다각형과 파란색 다각형의 꼭짓점 개수를 의미하는 두 정수 $N$과 $M$이 공백으로 구분되어 주어진다.

두 번째 줄부터 $N$개의 줄 중 $i$번째 줄에 빨간색 다각형의 $i$번째 꼭짓점 좌표를 나타내는 두 정수 $A_i$와 $B_i$가 공백으로 구분되어 주어진다. 꼭짓점 정보는 반시계 방향의 순서로 주어진다.

그 다음 줄부터 $M$개의 줄 중 $i$번째 줄에 파란색 다각형의 $i$번째 꼭짓점 좌표를 나타내는 두 정수 $C_i$와 $D_i$가 공백으로 구분되어 주어진다. 꼭짓점 정보는 반시계 방향의 순서로 주어진다.

출력

빨간색 다각형을 외곽으로, 파란색 다각형을 내곽으로 하여 둘러싸인 영역을 모두 밝히기 위해 필요한 촛불의 최소 개수를 출력하여라.

제한

• 3ドル\leq N, M \leq 500,000円$
• $-10^9 \leq A_i, B_i, C_i, D_i \leq 10^9$

힌트