- 强墙
- 2014-07-14 21:00:56 @
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 条评论
-
ERICFXY LV 8 @ 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