Shooting

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

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?

Input

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.

Output

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.

Sample Input

2 1 0.5 0.5 2 0.25 0.5 0.75 0.5

Sample Output

Case #1: 1.000000 Case #2: 0.625000 0.375000
Hint
Recommend eps equal or smaller than 1e-11.

Hint

zhoujiaqi2010

Source

2012 Multi-University Training Contest 3

提交代码