提示: 欢迎访问OurACM平台。
Problem 1908 Warehouse Location

Accept: 23    Submit: 69
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

There are N space stations in our vast space in the future. We use three-dimension coordinates of the point (x, y, z) to indicate the location of the station. The distance between point A (x1, y1, z1) and point B (x2, y2, z2) can be measured by Euclidean distance

To serve the residents in the space stations better, they plan to build a new warehouse. In order to save time, the location of the warehouse should be as near to the N space stations as possible. So we should minimize the maximum distance between the space station and the warehouse.

Given the location of the N space stations, your task is to find out the best location to build the new warehouse, and calculate the distance between the furthest space station and the warehouse.

Input

The first line of the input contains an integer T (T <= 10), indicating the number of cases. Each case begins with a line containing one integer n (2 <= n <= 500,000), the number of space stations in the space. The following n lines describe the location of the space station. Each line contains there integers x,y,z(-1,000,000 <= x,y,z <= 1,000,000) that describe the three-dimension coordinates of the space station. The positions of the n points are all distinct.

Output

For each test case, print a line containing the test case number (beginning with 1) and the distance between the furthest space station and the warehouse. Print your result rounded to 2 decimal places (as the format in sample).

Sample Input

1 6 1 0 0 -1 0 0 0 0 1 0 0 -1 0 2 0 0 -2 0

Sample Output

Case 1: 2.00

Source

2010年全国大学生程序设计邀请赛(福州)热身赛

Submit  Back  Status  Discuss