比赛 |
20091110 |
评测结果 |
C |
题目名称 |
高速公路 |
最终得分 |
0 |
用户昵称 |
maxiem |
运行时间 |
0.000 s |
代码语言 |
Pascal |
内存使用 |
0.00 MiB |
提交时间 |
2009-11-10 11:56:16 |
显示代码纯文本
program highway;
var
p:array [1..200] of record
x,y:integer;
end;
line:array [1..200,1..200] of record
x1,x2,y1,y2:integer;
end;
table:array [1..200,1..200] of double;
flag:array [1..200] of boolean;
dij:array [1..200] of double;
num,j,node,x1,y2,x2,y1,i,n,v,ed,p1,p2,point:integer;
tmp:int64;
t,min:double;
begin
fillchar (p,sizeof(p),0);
for i:=1 to 200 do for j:=1 to 200 do table[i,j]:=100000000.0;
fillchar (flag,sizeof(flag),0);
assign (input,'highway.in');
reset (input);
readln (n);point:=0;
for i:=1 to n do begin
readln (x1,y1,x2,y2);
line[i].x1:=x1;
line[i].x2:=x2;
line[i].y1:=y1;
line[i].y2:=y2;
p1:=0;p2:=0;
for j:=1 to point do begin
if (p[j].x=x1) and (p[j].y=y1) then p1:=j;
if (p[j].x=x2) and (p[j].y=y2) then p2:=j;
end;
if p1=0 then begin
inc(point);
p[point].x:=x1;
p[point].y:=y1;
p1:=point;
end;
if p2=0 then begin
inc(point);
p[point].x:=x2;
p[point].y:=y2;
p2:=point;
end;
tmp:=sqr(p[p1].x-p[p2].x)+sqr(p[p1].y-p[p2].y);
table[p1,p2]:=sqrt(tmp);
table[p2,p1]:=sqrt(tmp);
end;
for i:=1 to n do begin
for j:=1 to n do begin
if i<>j then begin
with line[i] do begin
a1:=(y2-y1)/(x2-x1);
b1:=y2-a*x2;
end;
with line[j] do begin
a2:=(y2-y1)/(x2-x1);
b2:=y2-a*x2;
end;
x:=b2-b1;
end;
end;
end;
readln (v);
ed:=p2;
close (input);
assign (output,'highway.out');
rewrite (output);
for i:=1 to point do dij[i]:=100000000.0;
num:=0;dij[1]:=0.0;
while num<point do begin
min:=maxlongint;inc(num);
for i:=1 to point do if (dij[i]<min) and (flag[i]=false) then begin
min:=dij[i];
node:=i;
end;
flag[node]:=true;
for i:=1 to point do begin
t:=dij[node]+table[node,i];
if (t<dij[i]) then dij[i]:=t;
end;
end;
writeln (dij[ed]/v:0:2);
close (output);
end.