eolymp
bolt
Try our new interface for solving problems
Məsələlər

Коммивояжер

Коммивояжер

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Согласно действующих международных торговых договоров, коммивояжер должен платить налоги на каждой границе, которую он пересекает. Поэтому ваша задача состоит в поиске минимального числа границ, которые должны быть пересечены во время путешествия между двумя странами. Мы имеем модель поверхности Земли в виде набора полигонов в трех измерениях, образующих замкнутую выпуклую 3D-форму, где каждый полигон соответствует одной стране. Вы не можете пересекать границу в точках, где встречаются более двух стран.

Входные данные Каждый тест состоит из строки, содержащей число стран c (4c6000 ), а затем идёт c строк, содержащих целые числа n x_1 y_1 z_1 ... x_n y_n z_n, описывающие (по порядку) n углов замкнутого многоугольника (3n20). Далее идёт строка с одним целым числом m (0 < m50), за которой следует m строк запросов c_a c_b, где c_a и c_b номера стран (страны пронумерованы начиная с 1 ). Нет точек, находящихся на линии, связывающей две другие точками, и −10^6x, y, z10^6 для всех точек. Нет двух несмежных ребер страны, имеющих общую точку. Входные данные завершает случай, когда c = 0, который не должен быть обработан.

Выходные данные Для каждого запроса выведите, сколько границ надо пересечь, чтобы добраться от c_a к c_b.

Nümunə

Giriş verilənləri #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
Çıxış verilənləri #1
2
1
Mənbə 2006 Nordic Collegiate Programming Contest, September 30, Problem F