Задачи
Коммивояжер
Коммивояжер
\includegraphics{https://static.e-olymp.com/content/42/42d8ca0f05688248befea56b17ecfad43957a85c.jpg}
Согласно действующих международных торговых договоров, коммивояжер должен платить налоги на каждой границе, которую он пересекает. Поэтому ваша задача состоит в поиске минимального числа границ, которые должны быть пересечены во время путешествия между двумя странами. Мы имеем модель поверхности Земли в виде набора полигонов в трех измерениях, образующих замкнутую выпуклую 3D-форму, где каждый полигон соответствует одной стране. Вы не можете пересекать границу в точках, где встречаются более двух стран.
\textbf{Входные данные} Каждый тест состоит из строки, содержащей число стран \textbf{c} (\textbf{4} ≤ \textbf{c} ≤ \textbf{6000} ), а затем идёт \textbf{c} строк, содержащих целые числа \textbf{n x_1 y_1 z_1 ... x_n y_n z_n}, описывающие (по порядку) \textbf{n }углов замкнутого многоугольника (\textbf{3} ≤ \textbf{n} ≤ \textbf{20}). Далее идёт строка с одним целым числом \textbf{m} (\textbf{0} < \textbf{m} ≤ \textbf{50}), за которой следует \textbf{m} строк запросов \textbf{c_a c_b}, где \textbf{c_a }и \textbf{c_b} номера стран (страны пронумерованы начиная с \textbf{1} ). Нет точек, находящихся на линии, связывающей две другие точками, и \textbf{−10^6} ≤ \textbf{x}, \textbf{y}, \textbf{z} ≤ \textbf{10^6} для всех точек. Нет двух несмежных ребер страны, имеющих общую точку. Входные данные завершает случай, когда \textbf{c = 0}, который не должен быть обработан.
\textbf{Выходные данные} Для каждого запроса выведите, сколько границ надо пересечь, чтобы добраться от \textbf{c_a} к \textbf{c_b}.
Входные данные #1
6 4 0 0 0 0 0 1 0 1 1 0 1 0 4 1 0 0 1 0 1 1 1 1 1 1 0 4 0 0 0 1 0 0 1 0 1 0 0 1 4 0 1 0 1 1 0 1 1 1 0 1 1 4 0 0 0 0 1 0 1 1 0 1 0 0 4 0 0 1 0 1 1 1 1 1 1 0 1 2 1 2 1 3 0
Выходные данные #1
2 1