Lots of Triangles
Description
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).
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.
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.
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.
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
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.