만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

통 속의 별

시간 제한2초메모리 제한512 MB

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

어려움10점 중 8점

유형
기하, 완전 탐색, 수학, 구현
정답자
아직 제출이 없습니다

문제

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

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

입력

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

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

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

출력

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

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

예제3

  1. 예제 1

    입력
    4
    1 0 0
    1 1 0
    0 0 0
    0 0 1
    
    예상 출력
    1.57
    
  2. 예제 2

    입력
    4
    -100 0 0
    10 0 10
    -10 -10 -10
    0 0 0
    
    예상 출력
    41938.65
    
  3. 예제 3

    입력
    7
    10 20 30
    0 0 0
    -100 1000 -20
    100 -20 33
    8 -7 900
    -100 -223 -23
    3 0 3
    
    예상 출력
    298192571.12