eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Червь в яблоке

Червь в яблоке

Вилли - червь, счастливо живущий в яблоке. До тех пор пока мерзкий человек не сорвал его и начал есть! Вилли необходимо бежать! По заданному описанию яблока (имеющего вид выпуклой фигуры в трехмерном пространстве) и списку возможных стартовых позиций в яблоке Вилли (заданных в виде трехмерных точек), определить наименьшее расстояние которое Вилли необходимо преодолеть, чтобы попасть на поверхность яблока из каждой точки. \InputFile Входные данные состоят из нескольких тестов. Каждый тест начинается со строки, содержащей одно целое число \textbf{n} (\textbf{4} ≤ \textbf{n} ≤\textbf{1000}) - количество вершин, задающих яблоко. В каждой из следующих \textbf{n} строк заданы три целых числа \textbf{x}, \textbf{y} и \textbf{z} (\textbf{-10000} ≤ \textbf{x}, \textbf{y}, \textbf{z} ≤ \textbf{10000}), каждая точка (\textbf{x}, \textbf{y}, \textbf{z}) находится либо на поверхности, либо внутри яблока. Яблоко представляет собой выпуклую оболочку этих точек. Никакие четыре точки не компланарны. За описанием яблока следует строка с целым числом \textbf{q} (\textbf{1} ≤ \textbf{q} ≤ \textbf{100000}) - количество запросов, то есть количество точек, в которых изначально может находиться Вилли внутри яблока. Каждая из следующих \textbf{q} строк содержит три целых числа \textbf{x}, \textbf{y} и \textbf{z} (\textbf{-10000} ≤ \textbf{x}, \textbf{y}, \textbf{z} ≤ \textbf{10000}), задающих точку (\textbf{x}, \textbf{y}, \textbf{z}) возможного начального положения Вилли. Все точки Вилли гарантированно лежат внутри яблока. Последняя строка содержит \textbf{0}. \OutputFile Для каждого запроса вывести в отдельной строке одно действительное число - наименьшее расстояние которое необходимо пройти Вилли чтобы выбраться из яблока. Число следует вывести с \textbf{4} десятичными знаками, используя стандартное \textbf{5} вверх / \textbf{4} вниз округление (то есть \textbf{2.12344} округляется до \textbf{2.1234}, \textbf{2.12345} округляется до \textbf{2.1235}).
Лимит времени 20 секунд
Лимит использования памяти 64 MiB
Входные данные #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
1.0000
2.8868
7.0000
2.0000
Источник The University of Chicago Invitational Programming Contest 2012 15 April 2012