ac1245.pas

这是在网络上搜集到的在东京大学的ACM上面解决的一些题目的源码

program tju1245;
const
  maxn=25;
  maxv=maxn*4+2;
  fail='Poor dropship crashed.';
var
  cx,cy:array[1..maxn]of longint;
  x,y:array[1..maxv]of longint;
  dist:array[1..maxv]of real;
  visit:array[1..maxv]of boolean;
  n,l,v,i,j,sx,sy,tx,ty:longint;
procedure add(x0,y0:longint);
  var
    i:longint;
  begin
    for i:=1 to n do
      if (abs(cx[i]-x0)<l) and (abs(cy[i]-y0)<l) then exit;
    inc(v);x[v]:=x0;y[v]:=y0;
  end;
function crosssgn(x0,y0,x1,y1,x2,y2:longint):shortint;
  var
    c:int64;
  begin
    dec(x1,x0);dec(y1,y0);
    dec(x2,x0);dec(y2,y0);
    c:=int64(x1)*y2-int64(x2)*y1;
    if c>0 then crosssgn:=1 else if c<0 then crosssgn:=-1 else crosssgn:=0;
  end;
function intersect(xa,ya,xb,yb,xc,yc,xd,yd:longint):boolean;
  begin
    intersect:=(crosssgn(xa,ya,xb,yb,xc,yc)*crosssgn(xa,ya,xb,yb,xd,yd)<0) and
               (crosssgn(xc,yc,xd,yd,xa,ya)*crosssgn(xc,yc,xd,yd,xb,yb)<0);
  end;
procedure go(a,b:longint);
  var
    i:longint;
    t:real;
  begin
    t:=dist[a]+sqrt(sqr(x[a]-x[b])+sqr(y[a]-y[b]));
    if t>=dist[b] then exit;
    for i:=1 to n do
      if intersect(x[a],y[a],x[b],y[b],cx[i]-l,cy[i]-l,cx[i]+l,cy[i]+l) or
         intersect(x[a],y[a],x[b],y[b],cx[i]-l,cy[i]+l,cx[i]+l,cy[i]-l) then exit;
    dist[b]:=t;
  end;
begin
  repeat
    read(n,l,sx,sy,tx,ty);l:=l shr 1;
    for i:=1 to n do read(cx[i],cy[i]);
    v:=0;add(sx,sy);add(tx,ty);
    if v<2 then begin writeln(fail);continue;end;
    for i:=1 to n do begin
      add(cx[i]-l,cy[i]-l);
      add(cx[i]-l,cy[i]+l);
      add(cx[i]+l,cy[i]+l);
      add(cx[i]+l,cy[i]-l);
    end;

    dist[1]:=0;for i:=2 to v do dist[i]:=3e38;j:=1;
    fillchar(visit,sizeof(visit),0);
    repeat
      visit[j]:=true;
      for i:=2 to v do
        if not visit[i] then
          go(j,i);
      j:=2;
      for i:=3 to v do
        if not visit[i] and (dist[i]<dist[j]) then j:=i;
    until j=2;
    if dist[2]<1e38 then writeln(dist[2]:0:3) else writeln(fail);
  until seekeof;
end.