题目描述

Farmer John has recently acquired a nice herd of $N$ goats for his field. Each goat $i$ will be tied to a pole at some position $P_i$ using a rope of length $L_i$. This means that the goat will be able to travel anywhere in the field that is within distance $L_i$ of the point $P_i$, but nowhere else. (The field is large and flat, so you can think of it as an infinite two-dimensional plane.)

Farmer John already has the pole positions picked out from his last herd of goats, but he has to choose the rope lengths. There are two factors that make this decision tricky:

• The goats all need to be able to reach a single water bucket. Farmer John has not yet decided where to place this bucket. He has reduced the choice to a set of positions $\{Q_1, Q_2, \ldots, Q_M\}$, but he is not sure which one to use.
• The goats are ill-tempered, and when they get together, they sometimes get in noisy fights. For everyone's peace of mind, Farmer John wants to minimize the area $A$ that can be reached by all the goats.

Unfortunately, Farmer John is not very good at geometry, and he needs your help for this part!

For each bucket position $Q_j$, you should choose rope lengths so as to minimize the area $A_j$ that can be reached by every goat when the bucket is located at position $Q_j$. You should then calculate each of these areas $A_j$.

Example

In the picture below, there are four blue points, corresponding to the pole positions: $P_1$, $P_2$, $P_3$, and $P_4$. There are also two red points, corresponding to the potential bucket positions: $Q_1$ and $Q_2$. You need to calculate $A_1$ and $A_2$, the areas of the two shaded regions.

输入格式

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

The next $N$ lines contain the positions $P_1, P_2, \ldots, P_N$, one per line. This is followed by $M$ lines, containing the positions $Q_1, Q_2, \ldots, Q_M$, one per line.

Each of these $N + M$ lines contains the corresponding position's $x$ and $y$ coordinates, separated by a single space.

输出格式

For each test case, output one line containing "Case #$x$: $A_1$ $A_2$ ... $A_M$", where $x$ is the case number (starting from 1), and $A_1$ $A_2$ ... $A_M$ are the values defined above. Answers with a relative or absolute error of at most $10^{-6}$ will be considered correct.

3
2 3
0 20
20 0
-20 10
40 20
0 19
4 2
0 0
100 100
300 0
380 90
400 100
1000 5
3 1
0 0
10 10
20 0
10 5

Case #1: 1264.9865911 1713.2741229 0.2939440
Case #2: 1518.9063729 1193932.9692206
Case #3: 0.0

提示

Limits

• All coordinates are integers between $-10,000$ and $10,000$.
• The positions $P_1, P_2, \ldots, P_N, Q_1, Q_2, \ldots, Q_M$ are all distinct and no three are collinear.

Small dataset (7 Pts, Test set 1 - Visible)

• Time limit: 30 3 seconds.
• $1 \leq T \leq 100$.
• $N = 2$.
• $1 \leq M \leq 10$.

Large dataset (25 Pts, Test set 2 - Hidden)

• Time limit: 120 12 seconds.
• $1 \leq T \leq 10$.
• $2 \leq N \leq 5,000$.
• $1 \leq M \leq 1,000$.