Convex Hull Surface Area

No attempts yetTime limit1sMemory limit128 MB

Problem

A three-dimensional shape is convex if, for any two points inside it, the line segment joining them lies entirely within the shape. For a set of points XX in three-dimensional space, the convex hull of XX is the smallest convex shape that contains every point of XX.

For example, let X={(0,0,0), (10,0,0), (0,10,0), (0,0,10)}X = \{(0,0,0),\ (10,0,0),\ (0,10,0),\ (0,0,10)\}. The convex hull of XX is the tetrahedron whose vertices are the points of XX. This tetrahedron contains the point (1,1,1)(1,1,1), so adding (1,1,1)(1,1,1) to XX would not change the hull.

Given XX, compute the surface area of its convex hull, rounded to the nearest integer.

Note: every face of a convex hull is a polygon. In this problem you may assume that at most 33 points of XX lie on any single face of the hull (so every face is a triangle).

Input

The input contains multiple test cases. Each test case begins with an integer nn (4n254 \le n \le 25), the number of points in XX. The next nn lines each contain three integers: the xx, yy, and zz coordinates of one point. Every coordinate satisfies 100x,y,z100-100 \le x, y, z \le 100.

The input ends with a line containing n=0n = 0, which must not be processed.

Output

For each test case, print a single line containing the surface area of the convex hull, rounded to the nearest integer (for example, 2.4992.499 rounds to 22, while 2.52.5 rounds to 33).

Hint

To avoid ambiguity from rounding, the test data is built so that every answer is at least 0.0010.001 away from a rounding boundary (for instance, an area is never exactly 2.49972.4997).