NAIPC 2017

Start

2017-04-15 09:00 AKDT

NAIPC 2017

End

2017-04-15 14:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -1738 days 10:28:19

5:00:00

0:00:00

Problem BStars 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