首页 > ACM题库 > HDU-杭电 > hdu 3444 The Volume of Simple Polyhedron待解决[解题报告]C++
2014
03-23

hdu 3444 The Volume of Simple Polyhedron待解决[解题报告]C++

The Volume of Simple Polyhedron

问题描述 :

Simple Polyhedron is the polyhedron which has a genus of zero(It hasn’t to be a convex polyhedron).
Given a convex polyhedron with n planes, there are m points on each plane.
If there is a hole on some plane, then the position of the hole will be given as a point or several points.
Looking from the outside to the inside, the order of the points is clockwise.
If there are holes:
The points on odd layers will be given in counterclockwise, and the points on the even layers will be given in clockwise. The points will be given in the topological order of the layers from the outside to the inside.
Your task is to calculate the volume of the polyhedron.

输入:

Multiple test cases.
Each case begins with an integer n (4<=n<=20), which is the number of planes.
There will be n blocks following, each block describes a plane.
Every block begins with an integer m, which is the number of the points on the plane.
Each of the following m lines contains 3 integers, which are the coordinate of the point on the plane.

Input ends with n=0.

输出:

Multiple test cases.
Each case begins with an integer n (4<=n<=20), which is the number of planes.
There will be n blocks following, each block describes a plane.
Every block begins with an integer m, which is the number of the points on the plane.
Each of the following m lines contains 3 integers, which are the coordinate of the point on the plane.

Input ends with n=0.

样例输入:

7
3
0 0 0
0 2 0
3 0 0
3
1 0 1
2 0 1
1 1 1
3
0 0 0
0 0 3
0 2 0
3
1 0 1
1 1 1
1 0 2
3
3 0 0
0 2 0
0 0 3
3
1 1 1
2 0 1
1 0 2
6
0 0 0
3 0 0
0 0 3
1 0 1
1 0 2
2 0 1
0

样例输出:

2.8333


  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。