Grazing Goats

Farmer John brought $N$ goats to his field. Goat $i$ is tied to a pole at position $P_i$ with a rope of length $L_i$. The goat can go anywhere within distance $L_i$ of the point $P_i$, and nowhere outside that. The field is large and flat, so treat it as an infinite two-dimensional plane.

The pole positions stay where Farmer John put them for his last herd, so only the rope lengths are still open. Two conditions make that choice tricky.

• Every goat has to reach one water bucket. Farmer John has not decided where the bucket goes. He narrowed the candidates down to $Q_1, Q_2, \dots, Q_M$, but he does not know which one he will use.
• The goats are ill-tempered, and they get into noisy fights when they gather. For everyone's peace of mind, Farmer John wants the area $A$ that every goat can reach to be as small as possible.

Farmer John is not good at geometry, so he needs help with this part.

For each bucket position $Q_j$, pick the rope lengths so that the area $A_j$ reachable by every goat is as small as possible when the bucket sits at $Q_j$, then compute that area $A_j$.

Figure

In the picture below, the four blue points are the pole positions $P_1, P_2, P_3, P_4$, and the two red points are the candidate bucket positions $Q_1$ and $Q_2$. The two shaded regions have areas $A_1$ and $A_2$.

The first line contains the number of test cases $T$. The $T$ test cases follow. Each test case begins with a line containing the integers $N$ and $M$.

The next $N$ lines contain the pole positions $P_1, P_2, \dots, P_N$, one per line, and the $M$ lines after that contain the candidate bucket positions $Q_1, Q_2, \dots, Q_M$, one per line.

Each of these $N + M$ lines holds the $x$ coordinate and the $y$ coordinate of the corresponding position, separated by a single space.

Limits

• Every coordinate is an integer between $-1\,000$ and $1\,000$.
• Within one test case, $P_1, \dots, P_N, Q_1, \dots, Q_M$ are all distinct, and no three of them are collinear.
• $1 \le T \le 5$
• $2 \le N \le 1\,000$
• $1 \le M \le 100$

For each test case, print one line in the format Case #x: A1 A2 ... AM, where x is the test case number starting from 1, and $A_1$ through $A_M$ are separated by single spaces.

Print each area rounded to exactly three digits after the decimal point. When the minimum area is 0, print 0.000.