통 속의 별

3차원 공간의 n개 점을 원기둥 하나에 모두 넣되 한 밑면에 점이 셋 이상 있어야 할 때, 가능한 원기둥 부피의 최솟값을 구해 소수 둘째 자리까지 출력한다.

어려움8기하완전 탐색수학구현아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

베라는 가까운 별의 분포를 연구하는 천문학자다. 별 하나는 3차원 공간의 점으로 나타낸다. 베라는 별을 모두 담는 원기둥을 하나 만들려고 한다. 원기둥의 축은 어느 방향으로든 놓을 수 있고, 두 밑면 중 적어도 한 밑면 위에 별이 세 개 이상 있어야 한다.

별을 모두 담는 원기둥의 최소 부피를 구하라.

입력

첫 줄에 별의 개수 nn이 주어진다. (4n10004 \le n \le 1\,000)

다음 nn개 줄에는 각각 세 정수 xx, yy, zz가 주어진다. 별 하나의 위치를 뜻한다. (1000x,y,z1000-1\,000 \le x, y, z \le 1\,000)

같은 위치에 있는 별은 없고, 한 평면 위에 놓인 별이 네 개 있는 경우도 없다.

출력

별을 모두 담는 원기둥의 최소 부피를 소수점 아래 둘째 자리까지 반올림해 한 줄에 출력한다. 예를 들어 부피가 1.5707961.570796\ldots이면 1.57을 출력한다.

모든 입력에서 정답은 소수점 아래 둘째 자리 반올림 경계에서 10310^{-3} 이상 떨어져 있다.