This page is still under construction.

Parts of this page are still being built. What you see may change.

Super Star

Time limit1sMemory limit128 MB

Summary
Read up to 29 points in 3D space and print the radius of the smallest sphere that contains all of them.
Level

Medium7 of 10

Topics
Geometry, Brute force
Solved
No attempts yet

Problem

During a voyage of the starship Hakodate-maru, researchers found strange synchronized movements of stars. Dr. Extreme heard about these observations and proposed a theory of super stars. The term has nothing to do with actors or singers. It is a theory in astronomy.

According to the theory, the stars we observe are not independent objects. Each one is a small part of a much larger object called a super star. A super star is filled with invisible transparent material, and only a few points inside it or on its surface shine. We observe those points as stars.

To test the theory, Dr. Extreme wants to write the equations of motion of a super star and compare their solutions with the observed movements of stars. As a first step he assumes that a super star is a sphere whose radius is the smallest one such that the sphere contains every given star inside it or on its surface. That assumption lets him estimate the volume of a super star, and the density of the invisible material is already known, so he also gets its mass.

Write a program that reads the positions of stars and finds the smallest sphere containing all of them inside it or on its surface. Ignore the size of a star and treat it as a point. Assume the universe is a Euclidean space.

Input

The input consists of several data sets. Each data set has the following format.

n
x1 y1 z1
x2 y2 z2
...
xn yn zn

The first line of a data set holds the number of points nn, where 1≤n≤291 \le n \le 29.

The next nn lines give the positions of the points in three-dimensional orthogonal coordinates (xi,yi,zi)(x_i, y_i, z_i). The three coordinates of one point appear on one line, separated by single spaces.

Each value is a decimal fraction between 0.00.0 and 100.0100.0, both ends included. Any two points are at least 0.010.01 apart.

A line containing a single 00 marks the end of the input.

Output

For each data set, print the radius of the smallest sphere containing all of the given points, one radius per line. Print the radius rounded to 5 digits after the decimal point. The answer of every data set stays far from a rounding boundary, so a computation with absolute error at most 10−710^{-7} prints the same digits.

Examples1

  1. Example 1

    Input
    4
    10.00000 10.00000 10.00000
    20.00000 10.00000 10.00000
    20.00000 20.00000 10.00000
    10.00000 20.00000 10.00000
    4
    10.00000 10.00000 10.00000
    10.00000 50.00000 50.00000
    50.00000 10.00000 50.00000
    50.00000 50.00000 10.00000
    0
    
    Expected output
    7.07107
    34.64102