98 条题解

  • 0
    @ 2008-10-29 21:55:05

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

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

    这样算的

    大概是平行四边形

  • 0
    @ 2008-10-29 18:31:49

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

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

    o为矩形中点

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

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

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

  • 0
    @ 2008-10-26 16:29:25

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

  • 0
    @ 2008-10-21 23:04:19

    第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;

  • 0
    @ 2008-10-11 20:12:23

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

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

    图建好了就好办了.

    Floyed或者Dijkstra.

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

  • 0
    @ 2008-10-05 21:18:41

    吐血113行程序终于AC

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

    要不然真不知道怎么搞

  • 0
    @ 2008-09-23 19:40:43

    编译通过...

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

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

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

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

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

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

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

    一次AC,DIJKSTRA!!

  • 0
    @ 2008-09-21 14:00:00

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

    编译通过...

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

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

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

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

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

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

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

  • 0
    @ 2008-09-21 14:41:58

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

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

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

    细节啊,细节。

  • 0
    @ 2008-09-16 07:27:29

    此题数据好YD.

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

  • 0
    @ 2008-09-15 17:12:54

    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]

  • 0
    @ 2008-09-10 23:15:58

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

  • 0
    @ 2008-09-09 19:30:54

    编译通过...

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

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

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

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

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

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

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

    floyed搞定

  • 0
    @ 2008-09-06 10:07:32

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

  • 0
    @ 2008-08-26 22:33:53

    50行搞定,floyed+预处理

  • 0
    @ 2008-08-22 16:55:41

    140行!AC的好痛苦!

    一定要有耐心!

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

  • 0
    @ 2008-07-17 19:56:33

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

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

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

  • 0
    @ 2007-11-16 11:42:15

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

  • 0
    @ 2007-11-14 11:32:45

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

  • 0
    @ 2007-11-12 11:37:18

    当心AB在一所城市里……

信息

ID
1119
难度
5
分类
图结构 | 最短路 点击显示
标签
递交数
2564
已通过
827
通过率
32%
被复制
16
上传者