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