比赛 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.