98 条题解
-
0
panfei LV 3 @ 2007-11-10 20:26:43
引自： nicolas大牛
"我晕哦
提交了n次都只过60%
结果是把dijkstra忘了，用了自创的不知名的算法在求最短路径确实正如下面几位所言，把出发那里的铁路先免费
再依靠“RT三角形斜边最长”求第四个机场......."我也是，用了2001的数据，过了3个点，但不知为何？
ps：我用的是4遍！！
-
0
-
0
zyffyz8002 LV 3 @ 2007-10-28 22:55:40
有第四个机场么……
一开始没看到……
wa的我很莫名其妙……
建图好了，一般不会有什么太大问题……
dijkstra -
0
ljj5112898 LV 3 @ 2007-10-23 17:44:02
一切同下
-
0
canbitwell LV 3 @ 2007-10-09 11:53:54
我为了简便，用一个4维交错数组做邻接矩阵
弗罗耶德 就需要六层循环……不过总循环次数和三层的 应该一样算第四个点用向量加减即可，找出对角线中点，然后加加减减即可。非对角顶点 + 该顶点到对角线中点的向量*2
有数据矩形不是正放的，那就判断边是否正交，对角线也确定就出来了
若(x2-x3)*(x1-x3)+(y2-y3)*(y1-y3)=0 则 对角线是1-2
点（x3 + ((x1+x2)*0.5 -x3)*2， y3 + ((y1+y2)*0.5 -y3)*2）
(x2-x1)*(x3-x1)+(y2-y1)*(y3-y1)=0 对角线3-2
(x1-x2)*(x3-x2)+(y1-y2)*(y3-y2)=0 对角线3-1 -
0
_Mithrandir_ LV 3 @ 2006-11-16 19:30:17
几何算法 判断矢量垂直
-
0
raulstarfans LV 3 @ 2006-11-01 16:49:55
还是floyd算法简单，一边ac
-
0
LV 0 @ 2006-10-06 19:47:04
不过要通过一个矩形的三个坐标求出另外一个坐标好象很麻烦.
我直接把矩形看成放得正规,然后求第4个点的坐标,得了60分.
panfei
LV 3
@ 2007-11-10 20:26:43
