2014
03-23

# 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.

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树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。