Stars in a Can

Time limit2sMemory limit512 MB

Summary

Place all n points in 3D inside one cylinder of any orientation, with at least three stars on one base, and print the minimum possible volume.

Level: Hard8 of 10
Topics: Geometry, Brute force, Math, Implementation
Solved: No attempts yet

Problem

Vera is an astronomer who studies how nearby stars are distributed. Each star is a point in three dimensional space. Vera wants to put every star inside one cylinder. The cylinder may point in any direction, and at least one of its two circular bases must hold three or more stars.

Find the smallest volume of a cylinder that contains every star.

Input

The first line contains the number of stars $n$ ( $4 \le n \le 1\,000$ ).

Each of the next $n$ lines contains three integers $x$ , $y$ and $z$ , the position of one star ( $-1\,000 \le x, y, z \le 1\,000$ ).

No two stars share a position, and no four stars lie on one plane.

Output

Print the smallest volume of a cylinder that contains every star, rounded to two digits after the decimal point, on one line. For example, print 1.57 when the volume is $1.570796\ldots$ .

In every input the answer is at least $10^{-3}$ away from a two decimal rounding boundary.

Examples3

Example 1
Input
```
4
1 0 0
1 1 0
0 0 0
0 0 1
```
Expected output
```
1.57
```

Example 2

Input

4
-100 0 0
10 0 10
-10 -10 -10
0 0 0

Expected output

41938.65

Example 3

Input

7
10 20 30
0 0 0
-100 1000 -20
100 -20 33
8 -7 900
-100 -223 -23
3 0 3

Expected output

298192571.12