A 3-dimensional shape is said to be convex if the line segment joining any two points in
the shape is entirely contained within the shape. Given a general set of points X in
3-dimensional space, the convex hull of X is the smallest convex shape containing all the
points.
For example, consider X = {(0, 0, 0), (10, 0, 0), (0, 10, 0), (0, 0, 10)}. The convex hull
of X is the tetrahedron with vertices given by X. Note that the tetrahedron contains the
point (1, 1, 1), so even if this point were added to X, the convex hull would not change.
Given X, your task is to find the convex hull of X.
NOTE: For this problem, you may assume that there's always exists a valid convex hull.
The input testdata will contain multiple test cases, each of which begins with an integer
n (4 <= n <= 400) indicating the number of points in X. This is followed by n lines, each
containing 3 integers giving the x, y and z coordinate of a single point. All coordinates
are between -500 and 500 inclusive. The end-of-input is marked by a test case with n = 0
and should not be processed.
For each test case, output an integer on a line indicating number of points on the surface
of the convex hull.
5 0 0 0 10 0 0 0 10 0 0 0 10 1 1 1 7 0 0 0 10 0 0 0 10 0 0 0 10 1 1 1 0 1 0 1 1 0 9 0 0 0 2 0 0 2 2 0 0 2 0 1 1 2 1 1 -2 1 1 -1 1 1 0 1 1 1 0
4 6 6
Migrated from old NTUJ.
| No. | Testdata Range | Score |
|---|