/ Vijos / 讨论 / 强墙 /

我惊呆了,第一个点竟然错?!

program p1013;
var a:array[1..140,1..140] of extended;
f:array[1..140] of extended;
b:array[1..140,1..2] of extended;
n:longint;
//
procedure init;
var b1,b2,b3,b4,b5:extended;
i:longint;
begin
readln(n);b[1,1]:=0;b[1,2]:=5;b[6*n+2,1]:=10;b[6*n+2,2]:=5;
for i:=1 to n do
begin
readln(b1,b2,b3,b4,b5);
b[6*(i-1)+2,1]:=b1;b[6*(i-1)+2,2]:=0;
b[6*(i-1)+3,1]:=b1;b[6*(i-1)+3,2]:=b2;
b[6*(i-1)+4,1]:=b1;b[6*(i-1)+4,2]:=b3;
b[6*(i-1)+5,1]:=b1;b[6*(i-1)+5,2]:=b4;
b[6*i,1]:=b1;b[6*i,2]:=b5;
b[6*i+1,1]:=b1;b[6*i+1,2]:=10;
end;
end;
//
function mk(i,j,k:longint):extended;
begin
exit(b[i,2]+((b[k*2,1]-b[i,1])/(b[j,1]-b[i,1]))*(b[j,2]-b[i,2]));
end;
//
procedure makegroup;
var i,j,k:longint;
t:boolean;
begin
for i:=1 to (6*n)+2 do
for j:=1 to (6*n)+2 do a[i,j]:=1000000;
for i:=1 to (6*n)+2 do
for j:=i+1 to (6*n)+2 do
if (b[i,1]<>b[j,1]) then
begin
t:=true;
for k:=1 to 3*n do
if (b[k*2,1]<b[j,1]) and (b[i,1]<b[k*2,1]) then
begin
if ((mk(i,j,k)<b[k*2+1,2]) and (mk(i,j,k)>b[k*2,2]))
then t:=false;
end else if (b[j,1]<b[k*2,1]) then break;
if t then
begin
a[i,j]:=sqrt(sqr(b[i,1]-b[j,1])+sqr(b[i,2]-b[j,2]));
a[j,i]:=sqrt(sqr(b[i,1]-b[j,1])+sqr(b[i,2]-b[j,2]));
end;
end;
end;
//
procedure main;
var i,j,k:longint;
begin
makegroup;
f[1]:=0;for i:=2 to (n*6)+2 do f[i]:=a[1,i];
for i:=1 to (n*6)+2 do
for j:=1 to (n*6)+2 do
for k:=1 to (n*6)+2 do
if a[j,k]+f[j]<f[k] then f[k]:=f[j]+a[j,k];
write(f[6*n+2]:0:2);
end;
//
begin
init;
main;
end.

2 条评论

  • @ 2014-08-01 15:19:40

    我是来看看我的头像的=。=

  • @ 2014-07-14 21:02:03

    program p1013;
    var a:array[1..140,1..140] of extended;
    f:array[1..140] of extended;
    b:array[1..140,1..2] of extended;
    n:longint;
    //
    procedure init;
    var b1,b2,b3,b4,b5:extended;
    i:longint;
    begin
    readln(n);b[1,1]:=0;b[1,2]:=5;b[6*n+2,1]:=10;b[6*n+2,2]:=5;
    for i:=1 to n do
    begin
    readln(b1,b2,b3,b4,b5);
    b[6*(i-1)+2,1]:=b1;b[6*(i-1)+2,2]:=0;
    b[6*(i-1)+3,1]:=b1;b[6*(i-1)+3,2]:=b2;
    b[6*(i-1)+4,1]:=b1;b[6*(i-1)+4,2]:=b3;
    b[6*(i-1)+5,1]:=b1;b[6*(i-1)+5,2]:=b4;
    b[6*i,1]:=b1;b[6*i,2]:=b5;
    b[6*i+1,1]:=b1;b[6*i+1,2]:=10;
    end;
    end;
    //
    function mk(i,j,k:longint):extended;
    begin
    exit(b[i,2]+((b[k*2,1]-b[i,1])/(b[j,1]-b[i,1]))*(b[j,2]-b[i,2]));
    end;
    //
    procedure makegroup;
    var i,j,k:longint;
    t:boolean;
    begin
    for i:=1 to (6*n)+2 do
    for j:=1 to (6*n)+2 do a[i,j]:=1000000;
    for i:=1 to (6*n)+2 do
    for j:=i+1 to (6*n)+2 do
    if (b[i,1]<>b[j,1]) then
    begin
    t:=true;
    for k:=1 to 3*n do
    if (b[k*2,1]<b[j,1]) and (b[i,1]<b[k*2,1]) then
    begin
    if ((mk(i,j,k)<b[k*2+1,2]) and (mk(i,j,k)>b[k*2,2]))
    then t:=false;
    end else if (b[j,1]<b[k*2,1]) then break;
    if t then
    begin
    a[i,j]:=sqrt(sqr(b[i,1]-b[j,1])+sqr(b[i,2]-b[j,2]));
    a[j,i]:=sqrt(sqr(b[i,1]-b[j,1])+sqr(b[i,2]-b[j,2]));
    end;
    end;
    end;
    //
    procedure main;
    var i,j,k:longint;
    begin
    makegroup;
    f[1]:=0;for i:=2 to (n*6)+2 do f[i]:=a[1,i];
    for i:=1 to (n*6)+2 do
    for j:=1 to (n*6)+2 do
    for k:=1 to (n*6)+2 do
    if a[j,k]+f[j]<f[k] then f[k]:=f[j]+a[j,k];
    write(f[6*n+2]:0:2);
    end;
    //
    begin
    assign(input,'p1013.in');assign(output,'p1013.out');
    reset(input);rewrite(output);
    init;
    main;
    close(output);
    end.

  • 1

信息

ID
1013
难度
6
分类
计算几何 点击显示
标签
(无)
递交数
2269
已通过
532
通过率
23%
被复制
15
上传者