F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

The Volume of Simple Polyhedron

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


Problem 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
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-11-23 01:19:30, Gzip enabled