18190번 - 촛불과 그림자 스페셜 저지

꼭짓점이 (A₁, B₁), (A₂, B₂), ···, (A_N, B_N)인 빨간색 볼록 N각형과, 꼭짓점이 (C₁, D₁), (C₂, D₂), ···, (C_M, D_M)인 파란색 볼록 M각형이 있다.

여기서 재미있는 점은 아래 그림과 같이, 빨간색 볼록 다각형 내부에 파란색 볼록 다각형이 완전하게 포함된다.

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

빨간색 볼록 다각형 내부이나, 파란색 볼록 다각형의 내부와 경계에 포함되지 않는 영역을 S라 하자. 아래 그림과 같이, 영역 S의 한 점에 촛불을 설치하면 노랑색 영역이 밝아지고, 회색 영역에는 그림자가 생긴다.

<그림 2> 밝혀진 영역과 그림자 영역

다각형의 정보와 촛불의 위치가 주어질 때, 그림자 영역의 넓이를 계산하는 프로그램을 작성하시오.

첫 번째 줄에 빨간색 다각형과 파란색 다각형의 꼭짓점 개수를 의미하는 두 자연수 N과 M, 쿼리의 개수를 의미하는 자연수 Q가 사이에 공백을 두고 주어진다.

두번째 줄부터 N개의 줄에 걸쳐, 빨간색 다각형의 꼭짓점 정보가 반시계 방향으로 주어진다. (i+1)번째 줄에는 두 정수 A_i와 B_i가 사이에 공백을 두고 주어진다(1 ≤ i ≤ N).

(N+2)번째 줄부터 M개의 줄에 걸쳐, 파란색 다각형의 꼭짓점 정보가 반시계 방향으로 주어진다. (N+i+1)번째 줄에는 두 정수 C_i와 D_i가 사이에 공백을 두고 주어진다(1 ≤ i ≤ M).

(N+M+2)번째 줄부터 Q개의 줄에 걸쳐, Q개의 쿼리에 관한 정보가 주어진다. (N+M+i+1)번째 줄에는 두 정수 X_i와 Y_i가 사이에 공백을 두고 주어진다(1 ≤ i ≤ Q). 이는 i번째 쿼리에서는 촛불을 (X_i, Y_i)에 설치함을 의미한다.

모든 Q개의 쿼리는 서로 독립적임에 유의하라.

첫 번째 줄부터 Q개의 줄에 걸쳐, 쿼리에 대한 답을 차례대로 출력한다.

만약 촛불의 위치가 빨간색 볼록 다각형의 외부나 경계에 존재한다면, "OUT"을 출력한다.

만약 촛불의 위치가 파란색 볼록 다각형의 내부가 경계에 존재한다면, "IN"을 출력한다.

위 두 가지 경우가 모두 아니라면, 그림자의 영역의 넓이를 출력한다.

실수에 대한 절대·상대 오차는 10^-6까지 허용된다.

모든 입력 데이터는 다음 조건을 만족한다.

• 3 ≤ N ≤ 10⁵
• 3 ≤ M ≤ 10⁵
• 1 ≤ Q ≤ 10⁵
• -10⁶ ≤ A_i ≤ 10⁶ (1 ≤ i ≤ N)
• -10⁶ ≤ B_i ≤ 10⁶ (1 ≤ i ≤ N)
• -10⁶ ≤ C_i ≤ 10⁶ (1 ≤ i ≤ M)
• -10⁶ ≤ D_i ≤ 10⁶ (1 ≤ i ≤ M)
• -10⁶ ≤ X_i ≤ 10⁶ (1 ≤ i ≤ Q)
• -10⁶ ≤ Y_i ≤ 10⁶ (1 ≤ i ≤ Q)