Описание
Внутрь квадрата с координатами левого нижнего угла (0,0) и координатами правого верхнего угла (100,100) поместили N квадратиков, стороны которых параллельны осям координат и имеют длину 5. Никакие два квадратика не имеют общих точек

Задание
Необходимо найти кратчайший путь из точки (0,0) в точку (100,100), который бы не пересекал ни одного из этих N квадратиков


Входные данные
В первой строке входного файла содержится целое число N (1≤N≤30), в каждой следующих N строк - координаты левого нижнего угла (x,y) очередного из квадратиков (0≤x,y≤95)

Выходные данные
Выведите в выходной файл координаты точек искомого пути, в которых меняется направление движения (включая начальную и конечную точки). Порядок точек в выходном файле должен соответствовать порядку точек в пути


Например:

SHORTCUT.IN
5
5 5
5 15
15 10
15 20
90 90

SHORTCUT.OUT
0 0
5 10
20 20
95 90
100 100





Идеи
Пересечение отрезка с квадратом, кратчайший путь в графе

Комментарии
Легко показать, что кратчайший путь может менять направление движения только в вершинах квадратиков (а также в начальной и конечной точках). Построим граф, вершины которого соответствуют всем указанным точкам. Если отрезок, соединяющий пару точек, не пересекает ни одного из квадратиков, то проведем между соответствующими вершинами графа ребро. Вес этого ребра положим равным длине рассматриваемого отрезка. Теперь осталось воспользоваться алгоритмом Дейкстры [Липский 88, п.3.3] для нахождения кратчайшего пути между двумя вершинами полученного графа.


Упражнения

  1. Действительно ли необходимо учитывать возможность прохождения пути через левые нижние и правые верхние углы квадратиков? Почему?

  2. Покажите, как проверить пересечение отрезка с квадратиком, не используя чисел с плавающей точкой (для этого вполне достаточно типа Integer)


 



 Решение

{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S-,T-,V-,X+,Y+}
{$M 16384,0,655360}
{$ifdef cpu87} {$N+} {$endif}

program shortcut;
type TPoint=record x,y: shortint end;
{$ifopt n+}
type real=double;
{$endif}
var N: byte;
    SA: array [1..40] of TPoint;
    M: byte;
    Ver: array [1..70] of TPoint;
    G: array [1..70,1..70] of boolean;
    R: array [1..70,1..70] of real;
 
function Inter(p1,p2,s: TPoint): boolean;
    function InSide(x1,y1,x2,y2,x,y: real): boolean;
    var t1,t2,t0,t: real;
    begin
      if abs(x1-x2)>abs(y1-y2) then
      begin
        t1:=x1;
        t2:=x2;
        t0:=x;
      end else
      begin
        t1:=y1;
        t2:=y2;
        t0:=y;
      end;
      if t1>t2 then
      begin
        t:=t1;
        t1:=t2;
        t2:=t;
      end;
      InSide:=(t1+1e-6<t0) and (t0<t2-1e-6);
   end;

function InterLine(p1,p2,p3,p4: TPoint): boolean;
    var a1,a2,b1,b2,c1,c2: longint; D: longint;
        x,y: real;
    begin
      a1:=p1.y-p2.y;
      b1:=p2.x-p1.x;
      c1:=integer(p1.x)*p2.y-integer(p2.x)*p1.y;
      a2:=p3.y-p4.y;
      b2:=p4.x-p3.x;
      c2:=integer(p3.x)*p4.y-integer(p4.x)*p3.y;
      D:=longint(a1)*b2-longint(a2)*b1;
      if D=0 then begin InterLine:=false; Exit end;
      x:=-(c1*b2-c2*b1)/D;
      y:=-(a1*c2-a2*c1)/D;
      InterLine:=InSide(p1.x,p1.y,p2.x,p2.y,x,y) and
                 InSide(p3.x,p3.y,p4.x,p4.y,x,y) ;
    end;
  var s1,s2,s3,s4: TPoint;
  begin
    Inter:=false;
      if (p1.x<s.x) and (p2.x<s.x) then Exit;
      if (p1.y<s.y) and (p2.y<s.y) then Exit;
      if (p1.y>s.y+5) and (p2.y>s.y+5) then Exit;
      if (p1.x>s.x+5) and (p2.x>s.x+5) then Exit; 
    s1:=s;
    s2.x:=s.x; s2.y:=s.y+5;
    s3.x:=s.x+5; s3.y:=s.y+5;
    s4.x:=s.x+5; s4.y:=s.y;
    Inter:=InterLine(p1,p2,s1,s2) or InterLine(p1,p2,s2,s3) or
           InterLine(p1,p2,s3,s4) or InterLine(p1,p2,s4,s1) or
           InterLine(p1,p2,s1,s3) or InterLine(p1,p2,s2,s4);
  end;
const UnLim=1e30;
var i,j,k,u,v,w: byte;
    lbl: array [1..70] of real;
    perm: array [1..70] of boolean;
    pred: array [1..70] of byte;
    MM: real;
    a1,b1,a2,b2: Shortint;
    rn: byte;
    res: array [1..60] of TPoint;
label NextVer,Step3;

begin
  Assign(Input,'shortcut.in'); Reset(Input);
  read(N);
  for i:=1 to N do read(sa[i].x,sa[i].y);
  Close(Input);
  M:=2;
  ver[1].x:=0; ver[1].y:=0;
  ver[2].x:=100; ver[2].y:=100;
  for i:=1 to N do
  begin
    inc(M);
    ver[m].x:=sa[i].x;
    ver[m].y:=sa[i].y+5;
    inc(M);
    ver[m].x:=sa[i].x+5;
    ver[m].y:=sa[i].y;
  end;
  inc(M);
  ver[m].x:=0; ver[m].y:=100;
  inc(M);
  ver[m].y:=0; ver[m].x:=100;
  for i:=1 to M do for j:=I+1 to M do
  if i=j then G[i,j]:=false else
  begin
    G[i,j]:=false; g[j,i]:=false;
    for k:=1 to N do if Inter(ver[i],ver[j],sa[k]) then Goto NextVer;
    G[i,j]:=true; g[j,i]:=true;
    R[i,j]:=sqrt(sqr(ver[i].x+0.0-ver[j].x)+sqr(0.0+ver[i].y-ver[j].y));
    R[j,i]:=R[i,j];
  NextVer:
  end;
  {   D E Y K S T R A    }
  for u:=1 to M do lbl[u]:=unlim;
  lbl[2]:=0;
  FillChar(perm,sizeof(perm),0);
  perm[2]:=true;
  for u:=1 to M do pred[u]:=u;
  i:=0; u:=2;
     { loop }
Step3:
  inc(i);
  for v:=1 to M do if not perm[v] then if g[u,v] then
  begin
    MM:=lbl[u]+R[u,v];
    if MM<lbl[v] then
    begin
      lbl[v]:=MM;
      pred[v]:=u;
    end;
  end;
  MM:=2*unlim;
  for v:=1 to M do if not perm[v] then
    if lbl[v]<MM then
    begin
      MM:=lbl[v];
      w:=v;
    end;
  perm[w]:=true;
  u:=w;
  if i<m-1 then Goto Step3;
  {  END Deykstra }
 
  assign(Output,'shortcut.out'); Rewrite(Output);
  u:=1;  rn:=1; res[1]:=ver[1];
  repeat
    u:=pred[u];
    inc(rn);
    res[rn]:=ver[u];
  until u=2;
  for i:=1 to rn do
  begin
    if (i>1) and (i<rn) then
    begin
      a1:=res[i-1].y-res[i].y;
      b1:=res[i].x-res[i-1].x;
      a2:=res[i-1].y-res[i+1].y;
      b2:=res[i+1].x-res[i-1].x;
      if integer(a1)*b2-integer(a2)*b1=0 then continue;
    end;
    writeln(res[i].x,' ',res[i].y);
  end;
  Close(OutPut);
end.
 

© Особенности национальных задач по информатике