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

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

사과 속의 벌레

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

요약
n개 점의 볼록 껍질로 주어진 볼록 다면체에서 내부 점마다 표면까지의 최단 거리를 구한다.
난이도

어려움10점 중 8점

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

문제

벌레 윌리(Willy)는 사과 속에서 행복하게 살고 있었습니다. 그런데 어떤 사람이 그 사과를 따서 베어 먹기 시작했습니다! 이제 윌리는 사과에서 탈출해야 합니다.

3차원 공간에서 볼록한 입체로 주어지는 사과의 정보와, 사과 내부에서 윌리가 있을 수 있는 여러 위치가 주어집니다. 각 위치에 대해, 윌리가 사과의 표면까지 도달하기 위해 이동해야 하는 최소 거리를 구하세요.

입력

입력은 여러 개의 테스트 케이스로 이루어집니다.

각 테스트 케이스의 첫 줄에는 사과를 나타내는 점의 개수 nn (4≤n≤10004 \le n \le 1000)이 주어집니다.

이어지는 nn개의 줄에는 각각 세 정수 xx, yy, zz (−10000≤x,y,z≤10000-10000 \le x, y, z \le 10000)가 주어지며, 각 점 (x,y,z)(x, y, z)는 사과의 표면 위에 있거나 사과 내부에 있습니다. 사과는 이 nn개 점의 볼록 껍질(convex hull)이며, 어떤 네 점도 한 평면 위에 있지 않습니다.

그다음 줄에는 질의의 개수 qq (1≤q≤1000001 \le q \le 100000)가 주어집니다. 이어지는 qq개의 줄에는 각각 세 정수 xx, yy, zz (−10000≤x,y,z≤10000-10000 \le x, y, z \le 10000)가 주어지며, 이는 윌리가 있을 수 있는 위치 (x,y,z)(x, y, z)를 나타냅니다. 모든 질의 위치는 사과 내부에 있음이 보장됩니다.

입력의 끝은 00 하나만 있는 줄로 표시됩니다.

출력

각 질의에 대해, 윌리가 사과의 표면까지 도달하기 위해 이동해야 하는 최소 거리를 한 줄에 하나씩 출력하세요. 값은 소수점 아래 정확히 네 자리까지 출력하며, 반올림(5 이상은 올림, 4 이하는 버림)을 사용합니다. 예를 들어 2.123442.12344는 2.12342.1234가 되고 2.123452.12345는 2.12352.1235가 됩니다. 답 사이에 불필요한 공백이나 빈 줄을 넣지 마세요.

예제3

  1. 예제 1

    입력
    6
    0 0 0
    100 0 0
    0 100 0
    0 0 100
    20 20 20
    30 20 10
    4
    1 1 1
    30 30 35
    7 8 9
    90 2 2
    0
    
    예상 출력
    1.0000
    2.8868
    7.0000
    2.0000
    
  2. 예제 2

    입력
    4
    0 0 0
    30 0 0
    0 30 0
    0 0 30
    4
    5 5 5
    1 1 1
    10 10 5
    1 14 14
    0
    
    예상 출력
    5.0000
    1.0000
    2.8868
    0.5774
    
  3. 예제 3

    입력
    5
    6 0 0
    -3 5 0
    -3 -5 0
    0 0 8
    0 0 -8
    4
    0 0 0
    0 0 5
    -1 0 0
    0 0 -5
    0
    
    예상 출력
    2.7379
    1.0267
    1.8727
    1.0267