Start

2017-04-15 19:00 CEST

NAIPC 2017

End

2017-04-16 00:00 CEST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -239 days 18:01:22

Time elapsed

5:00:00

Time remaining

0:00:00

Problem B
Stars in a Can

Vera is an astronomer studying locality of nearby star systems. The star systems can be thought of as 3D points in space. Vera would like to place a can around the stars. In other words, she would like to know what is the smallest volume cylinder that encloses the stars. The cylinder can be oriented in any direction. At least one base of the cylinder must have at least three stars.

Input

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input will contain a single integer $n$ ($4 \le n \le 1\, 000$), representing the number of stars.

Each of the next $n$ lines will contain three integers $x$, $y$ and $z$ ($-1\, 000 \le x, y, z \le 1\, 000$), representing the position of a single star. No two stars will be at the same position. No four stars will be coplanar.

Output

Output a floating point number representing the smallest volume cylinder that can enclose all the stars. Your answer must be accurate within a relative tolerance of $10^{-6}$.

Sample Input 1 Sample Output 1
4
1 0 0
1 1 0
0 0 0
0 0 1
1.57079633
Sample Input 2 Sample Output 2
4
-100 0 0
10 0 10
-10 -10 -10
0 0 0
41938.65135885
Sample Input 3 Sample Output 3
7
10 20 30
0 0 0
-100 1000 -20
100 -20 33
8 -7 900
-100 -223 -23
3 0 3
298192571.11934924