보로노이 섬

여러분 중에는 보로노이 섬에 얽힌 옛 이야기를 아는 사람도 있을 것이다. 이 섬에는 N명의 영주가 있었고, 그들은 늘 영토 분쟁을 벌였다. 섬 주민들은 그 분쟁에 지쳐 있었다.

어느 날 한 영리한 영주가 분쟁을 끝내고 섬을 공정하게 나누자고 제안했다. 그의 구상은 섬의 각 부분이 가장 가까운 성을 가진 영주에게 속하도록 섬을 나누는 것이었다. 이 방법은 오늘날 보로노이 분할이라고 불린다.

실제로 이 방법이 공정한지에는 여러 가지 면이 걸려 있다. 한 역사가에 따르면, 그 영리한 영주가 이 방법을 제안한 까닭은 다른 영주들보다 더 넓은 영역을 차지할 수 있었기 때문이었다.

여러분의 과제는 각 영주가 차지할 수 있는 영역의 넓이를 계산하는 프로그램을 작성하는 것이다. 보로노이 섬은 볼록한 모양이라고 가정해도 된다.

입력은 여러 개의 데이터셋으로 이루어진다. 각 데이터셋의 형식은 다음과 같다:

N M
Ix1 Iy1
Ix2 Iy2
...
IxN IyN
Cx1 Cy1
Cx2 Cy2
...
CxM CyM

N은 보로노이 섬의 꼭짓점 수이고, M은 영주의 수이다. (Ixi, Iyi)는 i번째 꼭짓점의 좌표이고, (Cxi, Cyi)는 i번째 영주의 성의 좌표이다.

입력은 다음 조건을 만족한다: 3 ≤ N ≤ 10, 2 ≤ M ≤ 10, -100 ≤ Ixi, Iyi, Cxi, Cyi ≤ 100. 꼭짓점은 반시계 방향으로 주어진다. 모든 좌표는 정수이다.

마지막 데이터셋 다음에는 두 개의 0이 있는 줄이 온다. 이 줄은 어떤 데이터셋의 일부도 아니며 처리해서는 안 된다.

각 데이터셋마다 각 영주가 차지하는 영역의 넓이를 절대 오차 10-4 이하로 출력한다. 소수점 아래 자릿수는 얼마든지 출력해도 된다. 출력하는 넓이의 순서는 입력에서 영주가 주어진 순서와 같아야 한다.