编程介的小学生 2019-09-23 13:25 采纳率: 20.5%
浏览 89

Traveling Salesman 怎么来实现

Problem Description
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.

Input
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.

Output
For each query, output the number of borders you must cross to go from ca to cb.

Sample Input
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

Sample Output
2
1

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 stata安慰剂检验作图但是真实值不出现在图上
    • ¥15 c程序不知道为什么得不到结果
    • ¥40 复杂的限制性的商函数处理
    • ¥15 程序不包含适用于入口点的静态Main方法
    • ¥15 素材场景中光线烘焙后灯光失效
    • ¥15 请教一下各位,为什么我这个没有实现模拟点击
    • ¥15 执行 virtuoso 命令后,界面没有,cadence 启动不起来
    • ¥50 comfyui下连接animatediff节点生成视频质量非常差的原因
    • ¥20 有关区间dp的问题求解
    • ¥15 多电路系统共用电源的串扰问题