| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 8 초 (추가 시간 없음) | 512 MB | 30 | 4 | 4 | 17.391% |
You are given a 3-dimensional convex polyhedron, and required to find its cut vertical to z-axis that maximizes the area of the resulting section.
There are multiple test cases in the input. Each test case begins with a single integer n (n ≤ 20), the number of faces of the polyhedron. The following n lines are the description of the faces. Each line is given in the format below.
m x1 y1 z1 x2 y2 z2 . . . xm ym zm
m (3 ≤ m < 20) is the number of vertices of the polygonal face. xi, yi and zi are the integral coordinates of the i-th vertex (0 ≤ xi, yi, zi < 10000). The distance between every pair of vertices is greater than 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.
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 10−5.
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
1.00 9.00