촛불과 그림자 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$