HDU3662 用来测试模板的，直接三维凸包，求凸包上的多边形个数。

# 3D Convex Hull

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1259 Accepted Submission(s): 652

Problem Description

There are N points in 3D-space which make up a 3D-Convex hull*. How many faces does the 3D-convexhull have? It is guaranteed that all the points are not in the same plane.

In case you don’t know the definition of convex hull, here we give you a clarification from Wikipedia: *Convex hull: In mathematics, the convex hull, for a set of points X in a real vector space V, is the minimal convex set containing X.

Input

There are several test cases. In each case the first line contains an integer N indicates the number of 3D-points (3< N <= 300), and then N lines follow, each line contains three numbers x, y, z (between -10000 and 10000) indicate the 3d-position of a point.

Output

Output the number of faces of the 3D-Convex hull.

Sample Input

7 1 1 0 1 -1 0 -1 1 0 -1 -1 0 0 0 1 0 0 0 0 0 -0.1 7 1 1 0 1 -1 0 -1 1 0 -1 -1 0 0 0 1 0 0 0 0 0 0.1

Sample Output

8 5

Source

2010 Asia Regional Harbin

------ 本文结束------
• 本文作者： kuangbin
• 本文链接： 450.html
• 版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！
0%