Shooting

There are some key points in a plane that can absorb everything inside the plane. The problem is, “A gun is shooting the plane, what’s the probability for the bullets to be absorbed by each key point”?
The plane is a rectangle whose height and width equals 1. Points in plane can be defined as ( x, y ), 0 < x < 1 , 0 < y < 1. When shooting, the bullets follow the distribution below:

After a bullet falls into the plane, it will be absorbed by the nearest key point. You are given the position of every key point. Can you tell me the probability absorbed by them?

The first line contains a single integer T (T <= 100), the number of test cases.

For each case, the first line of each case is a integer n(n <= 100), n means the number of key points.
Following n lines, each line contains two number a and b, (a , b) means the position of a key point.

For each case, you should print one line begin with “Case #”(quotations for explanation only) followed by the case number. Then, output a float number with 6 digits after decimal point, representing the probability that absorbed by each key point.

2
1
0.5 0.5
2
0.25 0.5
0.75 0.5

Case #1:
1.000000
Case #2:
0.625000
0.375000

Recommend eps equal or smaller than 1e-11.

BJTU

2012 Multi-University Training Contest 3