Convex Hull Surface Area
Time limit1sMemory limit128 MB
Given up to 25 points in 3D, compute the surface area of their convex hull with triangular faces, rounded to the nearest integer.
- Level
Medium7 of 10
- Topics
- Geometry, Implementation, Brute force
- Solved
- No attempts yet
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 in three-dimensional space, the convex hull of is the smallest convex shape that contains every point of .
For example, let . The convex hull of is the tetrahedron whose vertices are the points of . This tetrahedron contains the point , so adding to would not change the hull.
Given , 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 points of 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 (), the number of points in . The next lines each contain three integers: the , , and coordinates of one point. Every coordinate satisfies .
The input ends with a line containing , 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, rounds to , while rounds to ).
Hint
To avoid ambiguity from rounding, the test data is built so that every answer is at least away from a rounding boundary (for instance, an area is never exactly ).