Задачі
Комівояжер
Комівояжер
\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