Hide

Problem D
3D Printer

3D printing is a technique for manufacturing items from a digital template. The printer lays down layers of a polymer material, building an entire 3D object as a series of flat plates of varying shapes, stacked upon one another. The polymer is initially sticky enough so that the plates printed on top of one another will adhere. After the object dries or cures, the resulting objects can be quite durable.

Consider a 3D printer in which objects to be printed are described as a template, consisting of a combination of several convex polyhedra (i.e., flat-surfaced objects such that a line from one interior point to another interior point never passes outside the volume of the object). Write a program to determine the total volume of polymer required to sculpt an object from a given template.

Input

There will be a single test case in the input. This test case will begin with a line with a single integer $n$ ($1 \le n \le 100$) representing the number of polyhedra in that template.

The subsequent lines describe the n polyhedra. Each polyhedron begins with a line containing an integer $f$ ($3 < f < 30$), which is the number of faces on the polyhedron. Following that line is a series of lines describing polygons that comprise the faces. Each such line begins with an integer $v$ ($3 \le v \le 24$), which is the number of vertices. Following $v$ on the same line will be $3 \cdot v$ real numbers, representing the $v$ vertices as $(x,y,z)$ coordinates. For example, if $v=3$, then the line would be

    v x1 y1 z1 x2 y2 z2 x3 y3 z3

All coordinates will be in the range $[-100 \ldots 100]$. Vertices are presented in sequential order; there will be an edge of the polygon from $(x_1,y_1,z_1)$ to $(x_2,y_2,z_2)$, from $(x_2,y_2,z_2)$ to $(x_3,y_3,z_3)$, and so on. The polygons are closed, so there is an implied edge from the last vertex in a polygon back to the first. All of the vertices of a face will be coplanar. Edges will not cross, and each vertex will lie on exactly two edges. No three (or more) vertices in a polygon will be collinear. None of the polyhedra will overlap.

Output

Print a real number on its own line, indicating the volume of polymer required in cubic centimeters. The volume should be printed with a precision of two decimal places, rounded.

Sample Input 1 Sample Output 1
2
6
4 10 10 0 10 15 0 15 15 0 15 10 0
4 10 10 0 10 15 0 10 15 20 10 10 20
4 10 15 0 15 15 0 15 15 20 10 15 20
4 15 15 0 15 10 0 15 10 20 15 15 20
4 10 10 0 15 10 0 15 10 20 10 10 20
4 10 10 20 10 15 20 15 15 20 15 10 20
6
4 0 0 0 0 25 0 25 25 0 25 0 0
4 0 0 0 0 25 0 0 25 0.5 0 0 0.5
4 0 25 0 25 25 0 25 25 0.5 0 25 0.5
4 25 25 0 25 0 0 25 0 0.5 25 25 0.5
4 25 0 0 0 0 0 0 0 0.5 25 0 0.5
4 0 0 0.5 0 25 0.5 25 25 0.5 25 0 0.5
812.50

Please log in to submit a solution to this problem

Log in