2014
01-05

# Traveling Salesman

Long before the days of international trade treaties, a salesman would need to pay taxes at every border crossed. So your task is to find the minimum number of borders that need to be crossed when traveling between two countries. We model the surface of Earth as a set of polygons in three dimensions forming a closed convex 3D shape, where each polygon corresponds to one country. You are not allowed to cross at points where more than two countries meet.

Each test case consists of a line containing c, the number of countries (4 ≤ c ≤ 6000), followed by c lines containing the integers n x1 y1 z1 … xn yn zn, describing (in order) the n corners of a closed polygon (3 ≤ n ≤ 20). Then follows a line with one integer m (0 < m ≤ 50), and then m lines with queries ca cb, where ca and cb are country numbers (starting with 1). No point will be on the line between two connected points, and -106 ≤ x, y, z ≤ 106 for all points. No two non-adjacent edges of a country share a common point. The input is terminated by a case where c = 0, which should not be processed.

Each test case consists of a line containing c, the number of countries (4 ≤ c ≤ 6000), followed by c lines containing the integers n x1 y1 z1 … xn yn zn, describing (in order) the n corners of a closed polygon (3 ≤ n ≤ 20). Then follows a line with one integer m (0 < m ≤ 50), and then m lines with queries ca cb, where ca and cb are country numbers (starting with 1). No point will be on the line between two connected points, and -106 ≤ x, y, z ≤ 106 for all points. No two non-adjacent edges of a country share a common point. The input is terminated by a case where c = 0, which should not be processed.

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

1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同，其树的前、中、后序遍历是相同的，但在此处不能使用中序遍历，因为，中序遍历的结果就是排序的结果。经在九度测试，运行时间90ms，比楼主的要快。