시간 제한메모리 제한제출정답맞힌 사람정답 비율
8 초 (추가 시간 없음) 512 MB1000.000%

문제

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.

예제 입력 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

예제 출력 1

1.00
9.00