사과 속의 벌레
시간 제한15초메모리 제한128 MB
n개 점의 볼록 껍질로 주어진 볼록 다면체에서 내부 점마다 표면까지의 최단 거리를 구한다.
문제
벌레 윌리(Willy)는 사과 속에서 행복하게 살고 있었습니다. 그런데 어떤 사람이 그 사과를 따서 베어 먹기 시작했습니다! 이제 윌리는 사과에서 탈출해야 합니다.
3차원 공간에서 볼록한 입체로 주어지는 사과의 정보와, 사과 내부에서 윌리가 있을 수 있는 여러 위치가 주어집니다. 각 위치에 대해, 윌리가 사과의 표면까지 도달하기 위해 이동해야 하는 최소 거리를 구하세요.
입력
입력은 여러 개의 테스트 케이스로 이루어집니다.
각 테스트 케이스의 첫 줄에는 사과를 나타내는 점의 개수 ()이 주어집니다.
이어지는 개의 줄에는 각각 세 정수 , , ()가 주어지며, 각 점 는 사과의 표면 위에 있거나 사과 내부에 있습니다. 사과는 이 개 점의 볼록 껍질(convex hull)이며, 어떤 네 점도 한 평면 위에 있지 않습니다.
그다음 줄에는 질의의 개수 ()가 주어집니다. 이어지는 개의 줄에는 각각 세 정수 , , ()가 주어지며, 이는 윌리가 있을 수 있는 위치 를 나타냅니다. 모든 질의 위치는 사과 내부에 있음이 보장됩니다.
입력의 끝은 하나만 있는 줄로 표시됩니다.
출력
각 질의에 대해, 윌리가 사과의 표면까지 도달하기 위해 이동해야 하는 최소 거리를 한 줄에 하나씩 출력하세요. 값은 소수점 아래 정확히 네 자리까지 출력하며, 반올림(5 이상은 올림, 4 이하는 버림)을 사용합니다. 예를 들어 는 가 되고 는 가 됩니다. 답 사이에 불필요한 공백이나 빈 줄을 넣지 마세요.