(x1+x3)/2=xO=(x2+x4)/2

(y1+y3)/2=yo=(y2+y4)/2

这样算的

大概是平行四边形

为什么一定要用向量乘积呢。。。。。

不是可以用这个方程组求解吗？

o为矩形中点

(x1+x3)/2=xO=(x2+x4)/2

(y1+y3)/2=yo=(y2+y4)/2

这样做似乎也没错啊。。。

朴素SPFA+向量乘积 80行搞定 ;-)

第1567人。。。

这道题考察的重点是高中数学的向量的数量积，FLOYED算法

还有一个小地方。。用类似HASH的函数把坐标转到一个表示

坐标的矩阵中去，附向量处理的核心程序：

for i:= 1 to s do

for j:= 1 to 3 do

begin

x:=re; y:=re;

if j = 1 then begin x1:=re; y1:=re; x2:=re; y2:=re; end

else if j = 2 then begin x1:=re; y1:=re; x2:=re; y2:=re; end

else if j = 3 then begin x1:=re; y1:=re; x2:=re; y2:=re; end;

if (x1-x)*(x2-x)+(y1-y)*(y2-y) = 0 then begin re:=x1+x2-x; re:=y1+y2-y; end;

end;

几何建图的时候记得用向量.

然后记得考虑本城市和其他城市的情况.

图建好了就好办了.

Floyed或者Dijkstra.

最后枚举A-B的16条路径找出最小的就行了.

吐血113行程序终于AC

好险我在高一的时候学了向量

要不然真不知道怎么搞

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

一次AC，DIJKSTRA！！

真奇怪,图建对了,用DIJKSTRA不过,用FLOY就过了,神奇的地球,而且还0MS

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

建图好麻烦啊。关键是怎么算第四个点。

三点中距离最大的所对的那个点找出来然后用向量求第四个点。

循环里面赋最大值，害我提交了三次。

细节啊，细节。

此题数据好YD.

竟然有自己到自己的...

program p1119;

var

s,t,aa,bb:longint;

a,b:array[1..400] of longint;

f:array[1..400,1..400] of real;

procedure init;

var

xx,xx1,xx2,xx3,yy1,yy2,yy3,tt,k,i,j,ii,jj :longint;

x,y:array[1..4] of integer;

begin

readln(s,t,aa,bb);

for k:=1 to s do begin

readln(x[1],y[1],x[2],y[2],x[3],y[3],tt);

xx:=(x[1]-x[2])*(x[1]-x[2])+(y[1]-y[2])*(y[1]-y[2]);

xx1:=x[1]; xx2:=x[2]; yy1:=y[1]; yy2:=y[2]; xx3:=x[3];yy3:=y[3];

if (x[1]-x[3])*(x[1]-x[3])+(y[1]-y[3])*(y[1]-y[3])>xx then begin

xx:= (x[1]-x[3])*(x[1]-x[3])+(y[1]-y[3])*(y[1]-y[3]);

xx1:=x[1]; xx2:=x[3]; yy1:=y[1]; yy2:=y[3]; xx3:=x[2]; yy3:=y[2];

end;

if (x[2]-x[3])*(x[2]-x[3])+(y[2]-y[3])*(y[2]-y[3])>xx then begin

xx1:=x[2]; xx2:=x[3]; yy1:=y[2]; yy2:=y[3]; xx3:=x[1]; yy3:=y[1];

end;

x[4]:=xx1+xx2-xx3;

y[4]:=yy1+yy2-yy3;

for i:=1 to 4 do begin

a[(k-1)*4+i]:=x[i];

b[(k-1)*4+i]:=y[i];

end;

for i:=1 to 4 do

for j:=1 to 4 do begin

ii:=(k-1)*4+i; jj:=(k-1)*4+j;

f[ii,jj]:=sqrt( (a[ii]-a[jj])*(a[ii]-a[jj])+(b[ii]-b[jj])*(b[ii]-b[jj]) )*tt;

f[jj,ii]:=f[ii,jj];

end;

end;

end;

procedure main;

var

i,j,k:longint;

min:real;

begin

for i:=1 to 4*s do

for j:=1 to 4*s do

if ((i-1) div 4)((j-1) div 4) then begin

f:=sqrt( (a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j]) )*t;

f[j,i]:=f;

end;

for k:=1 to 4*s do

for i:=1 to 4*s do

for j:=1 to 4*s do

if ((i-1) div 4)((j-1) div 4) then

if f+f[k,j]

dijkstra就可以，就是建图太麻烦

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

floyed搞定

111行 。 用最长对角线作为矩形对角线。 dijkstra。

50行搞定，floyed+预处理

140行！AC的好痛苦！

一定要有耐心！

算法简单！预处理比较复杂！

预处理好烦 一个头，两个大 脑袋都快炸了

不过后面还是很简单的，，，

做出的感觉--》一身轻松

Floyed 竟然不超时,测试数据真够仁慈的

怎么都用的Floyd？这个是单源最短路，Dijkstra就行。正像楼下所说的，要判断两个机场是不是一个城市（借助mod 4），起点城市和终点城市的铁路价格赋值为0。计算一个城市第四个机场位置时用勾股定理判断谁是直角顶点（从楼下们的发言我发现自己走了弯路……直接判断三个边的大小就行。）唉，真麻烦。

当心AB在一所城市里……