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

문제

꼭짓점이 ($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_k},ドル $D_{M_k}$)인 파란색 볼록 $M_k$각형이 $K$개 있다.

아래 그림과 같이 촛불을 설치하면 노란색 영역이 밝아지고, 회색 영역에는 그림자가 생긴다.

촛불로 밝혀진 영역과 어두운 영역

노란빛 촛불만 옮기며 노는 게 질린 진홍이는 빨강(Red), 초록(Green), 파랑(Blue) 빛이 나는 촛불을 하나씩 구해왔다.

각각의 빛이 섞일 때 합성되는 색의 결과는 아래와 같다.

• 빨강(Red) + 초록(Green) = 노랑(Yellow)
• 빨강(Red) + 파랑(Blue) = 마젠타(Magenta)
• 초록(Green) + 파랑(Blue) = 시안(Cyan)
• 빨강(Red) + 초록(Green) + 파랑(Blue) = 하양(White)

그리고 모든 빛이 닿지 않아 그림자가 생기는 영역은 검정(Black)으로 표현할 수 있다.

빨간색 볼록 $N$각형과 $K$개의 파란색 볼록 $M_k$각형의 좌표와 빨강, 초록, 파랑 빛 촛불의 위치가 주어질 때, 빨강, 초록, 파랑, 노랑, 마젠타, 시안, 하양, 검정 영역의 넓이를 구해보자.

단, 빛이 무한대로 뻗어가기 때문에 빨간색 $N$각형 외부에 있는 촛불은 관찰 대상에서 제외한다.

각 촛불은 면적이 없는 점으로 가정한다. 어떠한 촛불도 없는 다각형의 내부는 검정이다.

빨간색 및 파란색 다각형 안에 있는 빛나는 영역의 넓이 및 그림자의 넓이를 모두 구해야 한다.

입력

첫째 줄에 빨간색 볼록 다각형의 꼭짓점 수 $N$이 주어진다. $(3 \le N \le 50)$

둘째 줄부터 $N$개의 줄에 걸쳐 빨간색 볼록 다각형의 꼭짓점 정보를 나타내는 두 정수 좌표 $A_i$와 $B_i$가 공백으로 구분되어 반시계 방향으로 주어진다. $(-1,000円 \le A_i, B_i \le 1,000円)$

$N+2$째 줄에 파란색 볼록 다각형의 총수를 나타내는 정수 $K$가 주어진다. $(1 \le K \le 16)$

이후 $K$개의 파란색 볼록 다각형에 대한 정보가 아래 형식으로 주어진다.

• 첫째 줄에 $k$번째 파란색 볼록 다각형의 꼭짓점 수 $M_k$가 주어진다. $(1 \le k \le K;\ 3 \le M_k \le 50;\ 3 \le \sum{M_k} \le 50)$
• 다음 $M_k$개의 줄에 걸쳐 $k$번째 파란색 볼록 다각형의 꼭짓점 정보를 나타내는 두 정수 좌표 $C_{kj}$와 $D_{kj}$가 공백으로 구분되어 반시계 방향으로 주어진다. $(1 \le j \le M_k;\ -1,000円 \le C_{kj}, D_{kj} \le 1,000円)$

마지막 줄에는 빨강, 초록, 파랑 빛 촛불을 설치할 3ドル$개의 좌표를 나타내는 6ドル$개의 정수 $R_{x}$ $R_{y}$ $G_{x}$ $G_{y}$ $B_{x}$ $B_{y}$가 공백으로 구분되어 주어진다. $(-1,000円 \le R_{x}, R_{y}, G_{x}, G_{y}, B_{x}, B_{y} \le 1,000円)$

모든 파란색 볼록 다각형들은 빨간색 볼록 다각형 내부에 완전하게 포함된다. 또한 서로 다른 두 개의 파란색 다각형은 서로 겹치거나 만나지 않는다.

모든 다각형의 두께는 0ドル$으로 가정하며, 촛불이 다각형의 변 위에 놓여있는 상황은 주어지지 않는다.

각 다각형에서 세 점이 일직선상에 놓여 있는 경우는 주어지지 않으며, 각 다각형의 넓이는 0ドル$보다 크다. 단, 서로 다른 두 다각형에 포함된 세 점은 일직선상에 있을 수 있다.

출력

8ドル$개의 줄에 걸쳐 빨강, 초록, 파랑, 노랑, 마젠타, 시안, 하양, 검정 영역의 넓이를 순서대로 출력한다.

실제 정답과 출력값의 절대 오차 또는 상대 오차가 10ドル^{-6}$ 이하라면 정답으로 인정한다.

제한

힌트