很容易就能看出这是一道最短路的题目，需要先建图，再求解，这道题难点在于建图
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
建图
首先要明确题目含义，每个城市含有四个飞机场，而这四个飞机场能连成一个矩形，但题目中仅给出了三个顶点，需要根据这三个顶点来确定第四个顶点，不妨先假设(X1,Y1)(X_1,Y_1)(X1 ,Y1 )和(X3,Y3)(X_3,Y_3)(X3 ,Y3 )为一组相对的顶点，那么剩下的(X2,Y2)(X_2,Y_2)(X2 ,Y2 )就必然与(X4,Y4)(X_4,Y_4)(X4 ,Y4 )为一组相对的顶点，此时X4=X1+X3−X2,Y4=Y1+Y3−Y2X_4=X_1+X_3-X_2,Y_4=Y_1+Y_3-Y_2X4 =X1 +X3 −X2 ,Y4 =Y1 +Y3 −Y2 ，
那该如何确定哪两个顶点是相对的呢？
先来回顾一下矩形的定义：至少有三个内角都是直角的四边形是矩形，
所以，若(X1,Y1)(X_1,Y_1)(X1 ,Y1 )和(X3,Y3)(X_3,Y_3)(X3 ,Y3 )为一组相对的顶点，由边(X1,Y1)(X_1,Y_1)(X1 ,Y1 ),(X2,Y2)(X_2,Y_2)(X2 ,Y2 )和(X2,Y2)(X_2,Y_2)(X2 ,Y2 ),(X3,Y3)(X_3,Y_3)(X3 ,Y3 )组成的夹角角度应为90°90°90°，这时候就该请出勾股定理了，定义如下：
如果三角形两条边的平方和等于第三边的平方，那么这个三角形就是直角三角形
所以只需要三个if语句就能判断第四个顶点的位置，代码如下：
其中f函数为两点距离的平方，
接下来就不说了，就是根据题目描述建边。由于每个城市有四个顶点，第iii个城市（下标从000开始）的第jjj个顶点记为i∗4+ji*4+ji∗4+j。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
求最短路
很容易看出这是一个稠密图，且SSS很小，4S4S4S最大也才400400400，用FloydFloydFloyd虽然简便，但640000006400000064000000有很大风险，这里采用堆优化的DijkstraDijkstraDijkstra（其实不用堆优化似乎更好？），入队时把(a−1)∗4+j(1≤j≤4)(a-1)*4+j(1≤j≤4)(a−1)∗4+j(1≤j≤4)加入，一旦找到(b−1)∗4+j(1≤j≤4)(b-1)*4+j(1≤j≤4)(b−1)∗4+j(1≤j≤4)就返回。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
完整代码
