Problem D
Airport
Input: Standard Input

Output: Standard Output

 

It is no coincidence that in no known language
does the phrase 'As pretty as an Airport' appear.

Douglas Adams

There is a small town with n houses. The town needs an airport. An airport is basically a very long, very straight road. Think of it as an infinite line. We need to build the airport such that the average distance from each house to the airport is as small as possible. However, no one wants to walk across the runway, so all of the houses must be on the same side of the airport. (Some houses may be a distance of zero away from the runway, but that's ok; we'll give them some free ear plugs.)

Where should we build the airport, and what will be the average distance?

Input
The first line of input gives the number of cases, N (<=65). N test cases follow. Each one is a line containing n (0 < n <= 10000), followed by n lines giving the xy-coordinates of the houses. All coordinates are integers with absolute value of at most 80,000.

 

Output

For each test case, output one line containing "Case #x:" followed by the average distance from the airport to the houses, with 3 digits after the decimal point. No answer will be within 10-5 of a round-off error case.

 

Sample Input                             Output for Sample Input

4
4
0 0
0 1
1 0
1 1
2
15035 39572
34582 39535
3
0 0
0 1
1 0
5
0 0
0 2
2 0
2 2
1 1
 
Case #1: 0.500
Case #2: 0.000
Case #3: 0.236
Case #4: 1.000

Problemsetters: Igor Naverniouk and Derek Kisman