Airport

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 4 4 00 01 10 11 2 15035 39572 34582 39535 3 00 01 10 5 00 02 20 22 11 It is no coincidence that in no known language does the phrase ’As pretty as an Airport’ appear. Douglas Adams

2/2 Sample Output Case #1: 0.500 Case #2: 0.000 Case #3: 0.236 Case #4: 1.000