Grazing Goats (Small)

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

The pole positions are already fixed, and Farmer John only has to pick the rope lengths. Two things make that choice awkward.

• Every goat has to reach a single water bucket. Farmer John has not decided where the bucket goes, but he has narrowed the choice down to $Q_1, Q_2, \dots, Q_M$.
• The goats are ill tempered and fight noisily when they end up in the same spot. Farmer John therefore wants the area $A$ that every goat can reach to be as small as possible.

For each bucket position $Q_j$, pick rope lengths that minimize the area $A_j$ reachable by every goat, then compute that $A_j$.

The picture below shows a field with four poles. 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$. In this problem there are always two poles.

The first line contains the number of test cases $T$. The first line of each test case contains the integers $N$ and $M$.

The next $N$ lines contain the pole positions $P_1, P_2, \dots, P_N$, one per line, followed by $M$ lines containing the bucket positions $Q_1, Q_2, \dots, Q_M$, one per line. Each of these $N + M$ lines contains the $x$ and $y$ coordinate of that point, separated by a single space.

Limits

• Every coordinate is an integer between $-1\,000$ and $1\,000$.
• Within one test case the $N + M$ points are distinct and no three of them lie on one line.
• $1 \le T \le 100$
• $N = 2$
• $1 \le M \le 10$

For each test case, print one line in the form Case #x: A1 A2 ... AM, where $x$ is the test case number starting from $1$ and $A_j$ is the area defined above.

Round every area and always print four digits after the decimal point, separating the values with a single space. For example, print 0.2939 for an area of $0.2939440$ and 10.7080 for an area of $10.708$.