C. Lots of Triangles
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given the three-dimensional Cartesian coordinates $$$(x_i,y_i,z_i)$$$ of $$$N$$$ robots. Find the minimum area difference between two distinct triangles that can be formed by taking three of these robots as vertices.

The time given for this problem is double the usual amount (2s).

Input

Line $$$1$$$: One integer, $$$N$$$

Lines $$$2…N+1$$$: Line $$$i+1$$$ contains three ordered triplets of three integers each: $$$x_{i,1},y_{i,1},z_{i,1},x_{i,2},y_{i,2},z_{i,2},x_{i,3},y_{i,3},z_{i,3}$$$. Consecutive integers are all separated by a space. Each ordered triplet represents a vertex of the $$$i$$$th triangle. It is guaranteed that for each $$$i$$$, no two ordered triplets in line $$$i+1$$$ are equal. In other words, the triangles in this problem may not degenerate to a line segment or a single point.

Output

Line $$$1$$$: One decimal, representing the minimum area difference between two distinct triangles out of these $$$N$$$ triangles. The output should be written to exactly five decimal places and rounded.

Example
Input
4
0 0 0 0 0 1 0 1 0
1 1 5 2 4 2 0 2 5
1 0 5 0 2 3 5 1 1
4 3 3 1 3 5 1 2 5
Output
1.11270
Note

$$$2≤N≤5000$$$

$$$0≤x_i,y_i,z_i≤10^9$$$

No two ordered triplets $$$(x_i,y_i,z_i)$$$ are repeated in the input.