﻿ Fuzhou University OnlineJudge ﻿  Problem 1908 Warehouse Location

## 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

Case 1: 2.00

## Source

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

Submit  Back  Status  Discuss 