아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

이상한 티끌, 하지만 괜찮아

면접 대비

시간 제한3초메모리 제한1024 MB

요약
정육면체 안의 3차원 점들이 주어질 때, 한 면에 수직으로 들어가는 드릴이 모든 점을 제거할 수 있는 최소 지름을 구한다. 각 좌표평면에 점을 투영했을 때의 최소 외접원 지름 중 최솟값이다.
난이도

보통10점 중 5점

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

문제

작품이 공중에 떠 있는 것처럼 보이는 설치 작품을 만들고 싶었던 예술가는 받침대로 쓸 투명 아크릴 정육면체를 주조했다. 그런데 주조 과정에서 작은 먼지 티끌 몇 개가 섞여 들어갔고, 지금은 그 외에는 투명한 정육면체 안에 핀 끝만 한 흠집 덩어리로 보인다.

그는 흠집이 들어 있는 부분을 드릴로 파낸 뒤, 파낸 부피를 새 투명 아크릴로 메우려 한다. 되도록 한 번의 드릴 작업으로 끝내고 싶다. 안정성을 위해 드릴은 정육면체의 한 면에 수직으로 들어가야 한다.

흠집의 (x,y,z)(x,y,z) 위치가 주어지고 흠집의 크기는 무시할 수 있다고 할 때, 한 번의 작업으로 흠집을 제거할 수 있는 가장 작은 드릴 날의 지름은 얼마인가?

드릴은 정육면체의 어느 면으로든 들어갈 수 있지만, 그 면에 직교하도록 위치해야 한다.

입력

첫 줄에는 흠집의 개수 NN이 정수로 주어진다. 3≤N≤5 0003 \leq N \leq 5\,000

다음 NN줄에는 각각 −1 000.0…1 000.0-1\,000.0\ldots 1\,000.0 범위의 실수 세 개가 주어지며, 이는 흠집 하나의 (x,y,z)(x,y,z) 좌표를 나타낸다. 각 수는 소수점 아래 최대 66자리까지 있을 수 있다. 소수점 아래 자리가 모두 0이면 소수점을 생략할 수 있다.

출력

모든 흠집을 제거할 수 있는 가장 작은 드릴 날의 지름을 출력한다.

절대 오차 또는 상대 오차가 10−410^{-4} 미만이면 정답으로 인정된다.

예제3

  1. 예제 1

    입력
    3
    1.0 0.0 1.4
    -1.0 0.0 -1.4
    0.0 1.0 -0.2
    
    예상 출력
    2.0000000000
    
  2. 예제 2

    입력
    5
    1.4 1.0 0.0
    -0.4 -1.0 0.0
    -0.1 -0.25 -0.5
    -1.2 0.0 0.9
    0.2 0.5 0.5
    
    예상 출력
    2.0000000000
    
  3. 예제 3

    입력
    8
    435.249 -494.71 -539.356
    455.823 -507.454 -539.257
    423.394 -520.682 -538.858
    446.507 -501.953 -539.37
    434.266 -503.664 -560.631
    445.059 -549.71 -537.501
    449.65 -506.637 -513.778
    456.05 -499.715 -561.329
    
    예상 출력
    49.9998293198