eolymp
bolt
Try our new interface for solving problems
Problems

3D Printer

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. \InputFile There will be several test cases in the input. Each test case will begin with a line with a single integer \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{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 \textbf{f} (\textbf{3} < \textbf{f} < \textbf{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 \textbf{v} (\textbf{3} ≤ \textbf{v} ≤ \textbf{24}), which is the number of vertices. Following \textbf{v}on the same line will be \textbf{3*v} real numbers, representing the \textbf{v} vertices as \textbf{(x,y,z)} coordinates. For example, if \textbf{v=3}, then the line would be \textbf{v x_1 y_1 z_1 x_2 y_2 z_2 x_3 y_3 z_3} All coordinates will be in the range \textbf{\[-100..100\]}. Vertices are presented in sequential order; there will be an edge of the polygon from \textbf{(x_1, y_1, z_1)} to \textbf{(x_2, y_2, z_2)}, from \textbf{(x_2, y_2, z_2)} to \textbf{(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 in any given test case will overlap. The input will end with a line with a single \textbf{0}. \OutputFile For each template, 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. Do not print any spaces. Do not print any blank lines between answers.
Time limit 1 second
Memory limit 64 MiB
Source The University of Chicago Invitational Programming Contest 2013, March 29-31, 2013