Задачі
Черв`як у яблуці
Черв`як у яблуці
Віллі - черв'як, який щастливо живе у яблуці. До тих пір доки меротна людина не зірвала його і почала їсти! Віллі необхідно тікати!
За заданим описом яблука (яке має вигляд опуклої фігури у тривимірному просторі) та списку можливих стартових позицій у яблуці Віллі (заданих у вигляді тривимірних точок), визначте найменшу відстань яку Віллі необхідно подолати, щоб потрапити на поверхню яблука з кожної точки.
\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}).
Вхідні дані #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