Коммивояжер
Коммивояжер
Согласно действующих международных торговых договоров, коммивояжер должен платить налоги на каждой границе, которую он пересекает. Поэтому ваша задача состоит в поиске минимального числа границ, которые должны быть пересечены во время путешествия между двумя странами. Мы имеем модель поверхности Земли в виде набора полигонов в трех измерениях, образующих замкнутую выпуклую 3D-форму, где каждый полигон соответствует одной стране. Вы не можете пересекать границу в точках, где встречаются более двух стран.
Входные данные Каждый тест состоит из строки, содержащей число стран c (4 ≤ c ≤ 6000 ), а затем идёт c строк, содержащих целые числа n x_1 y_1 z_1 ... x_n y_n z_n, описывающие (по порядку) n углов замкнутого многоугольника (3 ≤ n ≤ 20). Далее идёт строка с одним целым числом m (0 < m ≤ 50), за которой следует m строк запросов c_a c_b, где c_a и c_b номера стран (страны пронумерованы начиная с 1 ). Нет точек, находящихся на линии, связывающей две другие точками, и −10^6 ≤ x, y, z ≤ 10^6 для всех точек. Нет двух несмежных ребер страны, имеющих общую точку. Входные данные завершает случай, когда c = 0, который не должен быть обработан.
Выходные данные Для каждого запроса выведите, сколько границ надо пересечь, чтобы добраться от c_a к c_b.
Nümunə
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
2 1