The Volume of Simple Polyhedron

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 3444
64-bit integer IO format: %I64d      Java class name: Main

Description

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.

Input

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.

Output

Print the answer of each case in a separate line and the answer should be rounded to four decimal places.

Sample Input

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

Sample Output

2.8333

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .