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

Черв`як у яблуці

Черв`як у яблуці

Ліміт часу 20 секунд
Ліміт використання пам'яті 64 MiB

Віллі - черв'як, який щастливо живе у яблуці. До тих пір доки меротна людина не зірвала його і почала їсти! Віллі необхідно тікати!

За заданим описом яблука (яке має вигляд опуклої фігури у тривимірному просторі) та списку можливих стартових позицій у яблуці Віллі (заданих у вигляді тривимірних точок), визначте найменшу відстань яку Віллі необхідно подолати, щоб потрапити на поверхню яблука з кожної точки.

Вхідні дані

Вхідні дані складаються з декількох тестів. Кожен тест починається з рядка, який містить одне ціле число n (4n1000) - кількість вершин, які задають яблуко.

У кожному з наступних n рядків задано три цілих числа x, y та z (-10000x, y, z10000), кожна точка (x, y, z) знаходиться або на поверхні, або всередині яблука. Яблуко являє собою опуклу оболонку цих точок. Ніякі чотири точки не компланарні.

За описом яблука йде рядок з цілим числом q (1q100000) - кількість запитів, тобто кількість точок, у яких спочатку може знаходитись Віллі всередині яблука. Кожен з наступних q рядків містить три цілих числа x, y та z (-10000x, y, z10000), які задають точку (x, y, z) можливого початкового положення Віллі. Усі точки Віллі гарантовано лежать всередині яблука. Останній рядок містить 0.

Вихідні дані

Для кожного запиту вивести у окремому рядку одне дійсне число - найменшу відстань яку необхідимо пройти Віллі щоб вибратись з ябуока. Число слід вивести з 4 десятковими знаками, використовуючи стандартне 5 догори / 4 донизу округлення (тобто 2.12344 округлюється до 2.1234, 2.12345 округлюється до 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
Джерело The University of Chicago Invitational Programming Contest 2012 15 April 2012