3D Convex Hull -- ------ ---- You are given a large number of points in 3-space and must find the convex hull of these points. Input ----- For each test case, one line containing the name of the test case, followed by a line containing just `n', the number of points you are given, followed by n lines each containing `x y z', the coordinates of one of the points. The points are numbered 1 through n in the order that they appear in the input file. The xyz coordinates are all integers in the range from -1000 through +1000. 4 <= n <= 10,000. The input ends with an end of file. Output ------ For each test case, one line containing just the name of the test case, followed by a line containing just `m', the number of edges in the convex hull, followed by m lines, each containing `i j', where i and j are the numbers of the points that are the vertices of one of these edges. The input will be such that 4 <= m <= 100. An edge, by definition, is the edge of a face of the convex hull, and such a face can be any convex polygon. To simplify the code, the input will be such that each face is a triangle and all points on the convex hull will be vertices of faces. Thus no point will be in the interior of a face or on the line between two other points that are on the hull. All the hull face edges must be output in SORTED order. For an edge output as `i j', i < j is required. Edges with lower i values must be output first, and among edges with the same i values, those with lower j values must be output first. Sample Input ------ ----- TETRAHEDRON IN A CUBE 4 0 0 0 1 1 0 0 1 1 1 0 1 OCTAHEDRON 9 0 0 0 2 0 0 0 2 0 2 2 0 1 1 -2 1 1 2 1 1 -1 1 1 0 1 1 1 Sample Output ------ ------ TETRAHEDRON IN A CUBE 6 1 2 1 3 1 4 2 3 2 4 3 4 OCTAHEDRON 12 1 2 1 3 1 5 1 6 2 4 2 5 2 6 3 4 3 5 3 6 4 5 4 6 File: convexhull.txt Author: Bob Walton Date: Wed Oct 15 09:30:27 EDT 2008 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file. RCS Info (may not be true date or author): $Author: walton $ $Date: 2008/10/15 13:31:45 $ $RCSfile: convexhull.txt,v $ $Revision: 1.7 $