서커스 돔

시간 제한1초메모리 제한128 MB

요약
z축 위 꼭짓점과 바닥면을 갖는 원뿔 중 모든 3차원 점을 포함하면서 부피가 최소인 원뿔의 높이와 밑면 반지름을 구합니다.
난이도

어려움10점 중 8점

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

문제

순회 서커스단이 공중 공연을 위한 돔을 설계하려고 한다. 무대 위 공중에는 여러 장비와 지지대, 고정 장치가 설치되어 있으며, 돔은 무대 중심 위로 원뿔 모양으로 솟아 이 모든 것을 덮어야 한다. 돔 아래 공간은 냉방을 해야 하므로, 돔이 감싸는 부피는 최소가 되어야 한다.

공간상의 점 nn개가 주어진다. 점 (xi,yi,zi)(x_i, y_i, z_i)는 반드시 덮어야 하는 ii번째 물체의 위치이다 (1≤i≤n1 \le i \le n). 지면은 평면 z=0z = 0이고 zz가 커지는 방향이 위쪽이며, 무대 중심은 원점 (0,0,0)(0, 0, 0)이다.

돔의 꼭짓점은 (0,0,h)(0, 0, h) (h>0h > 0)에 위치한다. 돔은 밑면이 원점 (0,0,0)(0, 0, 0)을 중심으로 하고 반지름이 rr인 원이며 지면에 닿는 원뿔이다. 주어진 모든 점은 이 원뿔의 내부 또는 표면 위에 있어야 한다. 이러한 원뿔 중에서 부피가 가장 작은 것을 구하라.

입력

첫째 줄에 덮어야 하는 점의 개수 nn (1≤n≤10 0001 \le n \le 10\,000)이 주어진다. 다음 nn개의 줄에는 각각 ii번째 점의 좌표를 나타내는 세 실수 xix_i, yiy_i, ziz_i가 주어진다. 모든 좌표는 절댓값이 10001000 이하이고 소수점 아래 최대 두 자리까지 주어진다. 모든 ziz_i는 양수이며, xix_i 또는 yiy_i가 00이 아닌 점이 적어도 하나 존재한다.

출력

돔의 높이 hh와 밑면 반지름 rr을 공백 하나로 구분하여 한 줄에 출력한다. 두 값은 각각 소수점 아래 정확히 세 자리까지 반올림하여 출력한다 (예: 3.000). 부피가 최소인 돔은 유일하므로 두 값은 유일하게 결정된다.

예제5

  1. 예제 1

    입력
    1
    1.00 0.00 1.00
    
    예상 출력
    3.000 1.500
    
  2. 예제 2

    입력
    2
    1.00 0.00 1.00
    0.00 1.50 0.50
    
    예상 출력
    2.000 2.000
    
  3. 예제 3

    입력
    3
    1.00 0.00 1.00
    0.00 1.50 0.50
    -0.50 -0.50 1.00
    
    예상 출력
    2.000 2.000
    
  4. 예제 4

    입력
    1
    2.00 0.00 2.00
    
    예상 출력
    6.000 3.000
    
  5. 예제 5

    입력
    1
    3.00 4.00 5.00
    
    예상 출력
    15.000 7.500