eolymp
bolt
Try our new interface for solving problems
Problems

Cut out

Cut out

You are given a \textbf{3}-dimensional convex polyhedron, and required to find its cut vertical to \textbf{z}-axis that maximizes the area of the resulting section. \InputFile There are multiple test cases in the input. Each test case begins with a single integer \textbf{n} (\textbf{n} ≤ \textbf{20}), the number of faces of the polyhedron. The following \textbf{n} lines are the description of the faces. Each line is given in the format below. \textbf{m x_1 y_1 z_1 x_2 y_2 z_2 ... x_m y_m z_m} \textbf{m} (\textbf{3} ≤ \textbf{m} < \textbf{20}) is the number of vertices of the polygonal face. \textbf{x_i}, \textbf{y_i} and \textbf{z_i} are the integral coordinates of the \textbf{i}-th vertex (\textbf{0} ≤ \textbf{x_i}, \textbf{y_i}, \textbf{z_i} < \textbf{10000}). The distance between every pair of vertices is greater than \textbf{0.01}. The end of input is indicated by a line containing only a single zero. It is guaranteed that a set of polygons given as a test case forms a convex polyhedron. \OutputFile Output the area of the largest cutting plane in one line for each test case. The area may have an arbitrary number of digits after the decimal point, but should not contain an error greater than \textbf{10^\{−5\}}.
Time limit 1 second
Memory limit 64 MiB
Input example #1
6
4 0 0 0 1 0 0 1 1 0 0 1 0
4 0 0 0 1 0 0 1 0 1 0 0 1
4 0 0 0 0 1 0 0 1 1 0 0 1
4 1 1 1 0 1 1 0 1 0 1 1 0
4 1 1 1 0 1 1 0 0 1 1 0 1
4 1 1 1 1 0 1 1 0 0 1 1 0
6
4 0 1 2 0 3 2 4 3 2 4 1 2
4 1 0 0 3 0 0 3 4 0 1 4 0
4 0 1 2 4 1 2 3 0 0 1 0 0
4 4 3 2 0 3 2 1 4 0 3 4 0
4 0 3 2 0 1 2 1 0 0 1 4 0
4 4 1 2 4 3 2 3 4 0 3 0 0
0
Output example #1
1.00000000
9.00000000
Source ACM International Collegiate Programming Contest, Summer Camp (2nd Day), Tokyo, 2005–9–24