잘라내기
시간 제한8초메모리 제한512 MB
다면체를 이루는 면들이 주어질 때, z축에 수직인 평면으로 자른 단면의 넓이 중 최댓값을 구한다.
문제
3차원 볼록 다면체가 주어진다. 이 다면체를 z축에 수직인 평면으로 잘랐을 때 생기는 단면의 넓이가 최대가 되도록 하는 단면을 구하시오.
입력
입력에는 여러 개의 테스트 케이스가 들어 있다. 각 테스트 케이스의 첫 줄에는 다면체의 면의 개수 n (n ≤ 20)이 주어진다. 다음 n개의 줄에는 각 면의 정보가 주어진다. 각 줄은 아래 형식으로 주어진다.
m x1 y1 z1 x2 y2 z2 . . . xm ym zm
m (3 ≤ m < 20)은 다각형 면의 꼭짓점 개수이다. xi, yi, zi는 i번째 꼭짓점의 정수 좌표이다 (0 ≤ xi, yi, zi < 10000). 모든 꼭짓점 쌍 사이의 거리는 0.01보다 크다.
입력의 끝은 0 하나만 있는 줄로 나타낸다.
한 테스트 케이스로 주어지는 다각형들이 볼록 다면체를 이룸이 보장된다.
출력
각 테스트 케이스마다 최대 넓이를 갖는 절단면의 넓이를 한 줄에 출력한다. 넓이는 소수점 아래 자릿수가 몇 자리든 상관없지만, 오차가 10−5보다 크면 안 된다.