풀을 뜯는 Google 염소들

Farmer John은 최근 자신의 들판을 위해 훌륭한 N마리의 염소 떼를 마련했다. 각 염소 i은 길이가 $L_{i}$인 밧줄을 사용하여 어떤 위치 $P_{i}$에 있는 기둥에 묶인다. 이는 염소가 점 $P_{i}$에서 거리 $L_{i}$ 이내인 들판의 어느 곳으로든 이동할 수 있지만, 그 밖의 곳으로는 이동할 수 없다는 뜻이다. (들판은 넓고 평평하므로 무한한 이차원 평면이라고 생각해도 된다.)

Farmer John은 이전 염소 떼를 위해 정해 두었던 기둥 위치를 이미 가지고 있지만, 밧줄의 길이는 선택해야 한다. 이 결정을 까다롭게 만드는 요인은 두 가지이다.

• 모든 염소가 하나의 물 양동이에 도달할 수 있어야 한다. Farmer John은 아직 이 양동이를 어디에 놓을지 결정하지 않았다. 후보를 위치들의 집합 {$Q_{1}$, $Q_{2}$, ..., $Q_{M}$}로 줄였지만, 어느 위치를 사용할지는 확신하지 못하고 있다.

• 염소들은 성질이 사나워서 함께 모이면 때때로 시끄럽게 싸운다. 모두의 평온을 위해, Farmer John은 모든 염소가 도달할 수 있는 영역의 넓이 A를 최소화하려고 한다.

안타깝게도 Farmer John은 기하학에 능숙하지 않아서 이 부분에 당신의 도움이 필요하다!

각 양동이 위치 $Q_{j}$에 대해, 양동이가 위치 $Q_{j}$에 있을 때 모든 염소가 도달할 수 있는 영역의 넓이 $A_{j}$가 최소가 되도록 밧줄 길이를 선택해야 한다. 그런 다음 이 넓이들 $A_{j}$을 각각 계산해야 한다.

예제

아래 그림에는 기둥 위치에 해당하는 네 개의 파란색 점 $P_{1}$, $P_{2}$, $P_{3}$, $P_{4}$가 있다. 또한 가능한 양동이 위치에 해당하는 두 개의 빨간색 점 $Q_{1}$와 $Q_{2}$가 있다. 두 음영 영역의 넓이인 $A_{1}$와 $A_{2}$을 계산해야 한다.

제한

메모리 제한: 1GB. 모든 좌표는 -10,000와 10,000 사이의 정수이다. 위치 $P_{1}$, $P_{2}$, ..., $P_{N}$, $Q_{1}$, $Q_{2}$, ..., $Q_{M}$은 모두 서로 다르며, 어떤 세 위치도 한 직선 위에 있지 않다.

작은 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 30초. 1 ≤ T ≤ 100. N = 2. 1 ≤ M ≤ 10.

큰 데이터 세트 (테스트 세트 2 - 비공개)

시간 제한: 120초. 1 ≤ T ≤ 10. 2 ≤ N ≤ 5,000. 1 ≤ M ≤ 1,000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 N과 M이 담긴 줄로 시작한다.

다음 N개의 줄에는 위치 $P_{1}$, $P_{2}$, ..., $P_{N}$가 한 줄에 하나씩 주어진다. 이어지는 M개의 줄에는 위치 $Q_{1}$, $Q_{2}$, ..., $Q_{M}$가 한 줄에 하나씩 주어진다.

이 N + M개의 각 줄에는 해당 위치의 x좌표와 y좌표가 하나의 공백으로 구분되어 주어진다.

각 테스트 케이스마다 "Case #x: $A_{1}$ $A_{2}$ ... $A_{M}$"을 포함하는 한 줄을 출력한다. 여기서 x는 케이스 번호(1부터 시작)이고, $A_{1}$ $A_{2}$ ... $A_{M}$은 위에서 정의한 값들이다. 상대 오차 또는 절대 오차가 최대 10^{-6}인 답은 정답으로 간주한다.