It is 2180 AD, the human race has just started to abandon the earth and spread the civilization in space. ACM (Association for Cosmic Machinism) is in charge of this whole relocation process and this process is funded mostly by IBM (Inter-planet Ballistic Machines). Thousands of space cities are built in the outer space and to maintain universal business hour (Sunrises and sets at the same time in all space cities) they are built on the same imaginary plane. So the location of the cities can be expressed as two-dimensional Cartesian coordinates. The cities are located far away from one another and the only way of going from one city to another is by using shuttle rockets. But from previous experience ACM knows that traveling by roads is a lot cheaper than traveling by rockets. So they have decided to build some roads. But building roads between every pair of cities is very expensive. So they are planning to build a super space-way (SSW) that will be a straight road. When someone needs to travel from a city c1 to city c2, he first travels from c1 to the nearest point of SSW with a rocket, and moves along the SSW to the point, which is nearest to c2. Then from there he goes to c2 using another rocket. The cost of moving along the road is proportional to the distance but cost of flying on rockets is proportional to the square of the distance. So you have to build the SSW in such a position so that total cost of traveling in a calendar year by rockets is minimized. You can assume that:
2/2 Output For each test case produce Q + 2 lines of output. The first line contains the case number followed by a colon. The second line contains a floating-point number which denotes the minimum average cost per rocket flight for the optimal super space way (Assuming all cities are ordinary). This line is followed by Q lines, one line for each query. This line contains the serial of query followed by a floating-point number. This number denotes the minimum average cost for the optimal super space way assuming that S-th city is a super city and all other cities are ordinary. All floating-point numbers in the output should have five digits after the decimal point. Look at the output for sample input for details. You can assume that for all floating-point outputs an absolute error less than 10−5 will be ignored. Sample Input 52 464.9900 243.2652 463.9409 772.4632 201.9822 561.6255 695.8948 933.4567 226.0628 93.1435 32 43 42 27.1679 304.2512 27.7639 16.2479 921.9150 863.0064 167.6203 929.5471 22 23 00 Sample Output Case 1: 16172.49971 1: 14289.23473 2: 11558.37654 Case 2: 53198.72595 1: 47995.33546 2: 41543.27604