Convex Hull Surface Area in 3D

Given n points in 3-dimensional space, your task is to compute the total surface area of the convex hull that encloses these points.

The convex hull is defined as the smallest convex polyhedron that contains all the points. The surface area is the sum of the areas of all its polygonal faces. Note that if a face has more than three vertices, you should compute the area of the entire polygon (by first determining the convex polygon in that plane).

Notice: It is guaranteed that the input points are in a general position (i.e. not all coplanar overall except in degenerate cases) so that the convex hull is well–defined.

Mathematical Formulation:

For a plane with unit normal \(\mathbf{n}\) and offset \(d\) (i.e. equation \(\mathbf{n} \cdot \mathbf{x} + d = 0\)), a set of points \(P\) is on the same side of the plane if

\[ \mathbf{n} \cdot \mathbf{p} + d \ge 0 \quad \text{for all } \mathbf{p} \in P \quad \text{or} \quad \mathbf{n} \cdot \mathbf{p} + d \le 0 \quad \text{for all } \mathbf{p} \in P. \]

inputFormat

The first line contains an integer n (\(3 \le n \le 100\)), the number of points in space.

Each of the following n lines contains three real numbers \(x\), \(y\), and \(z\) denoting the coordinates of a point. The coordinates are separated by spaces.

outputFormat

Output a single floating point number representing the surface area of the convex hull. The answer will be considered correct if its absolute or relative error does not exceed \(10^{-6}\).

sample

4
0 0 0
1 0 0
0 1 0
0 0 1

2.366025