program trumpiausias_kelias;
  { 69 u‘davinys }
  const maxn = 30; { maksimalus kvadrat‚li— skai‡ius }
  type grafas = array [0..maxn*2 + 1, 0..maxn*2 + 1] of real;
                {  graf… reikia traukti ir tažk… (0, 0) bei (100, 100) }
       koordinates = array [0..maxn*2 + 1] of record
                                                x, y : integer
                                              end;
                 { vis— reikaling— grafo virž–ni— koordinat‚s }
       atstumai = array [0..2*maxn + 1] of real;
       kelias = array [0..2*maxn + 1] of integer;
       aibe = set of 0..2*maxn+1;

       { ‘emiau suražyti global–s kintamieji }
       var n : integer; { kvadrat‚li— skai‡ius }
           g : grafas;
           koord : koordinates; { grafo virž–ni— koordinat‚s }
           pi : kelias;

  procedure ivedimas;
    { veda pradinius duomenis - kvadrat‚li— skai‡i— n }
    { ir kvadrat‚li— koordinates. Pastaruosius iž karto }
    { perskai‡iuoja  grafo virž–ni— koordinates }
    { rezultatai - global–s kintamieji n ir koord }
    var f : text;
        i, a, b : integer;
  begin
    assign (f, 'kelias.dat');
    reset (f);
    readln (f, n);
    for i := 1 to n do
      begin
         readln (f, a, b);
         { apatinio dežiniojo kampo koordinat‚s }
         koord [2 * i - 1].x := a;
         koord [2 * i - 1].y := b + 5;
         { viržutinio kairiojo kampo koordinat‚s }
         koord [2 * i].x := a + 5;
         koord [2 * i].y := b
      end;
    { tažk— (0, 0) ir (100, 100) koordinat‚s }
    koord[0].x := 0;
    koord[0].y := 0;
    koord[2 * n + 1].x := 100;
    koord[2 * n + 1].y := 100
  end;

  function tiese (a, b, c : integer) : integer;
    { tikrina, kurioje ties‚s, einan‡ios per tažkus a ir b }
    { pus‚je yra tažkas c  }
    { pradiniai duomenys - globalus kintamasis koord }
    var k, d : integer;
  begin
    k := (koord[c].x - koord[a].x) * (koord[b].y - koord[a].y);
    d := (koord[c].y - koord[a].y) * (koord[b].x - koord[a].x);
    if k = d then tiese := 0 { tažkas kerta tiesŠ }
       else if k < d then tiese := 1
                     else tiese := -1
 end;

  procedure grafo_sudarymas;
    { pagal turimas grafo virž–ni— koordinates sudaro graf… - }
    { t. y. suskai‡iuoja atstumus tarp vis— grafo virž–ni— }
    { pradiniai duomenys - n ir koord }
    { rezultatas - grafas g }
    var i, j, k : integer;
        kerta : boolean; { ar atkarpa kerta kur nors kvadrat‚l }
  begin
    for i := 0 to 2 * n + 1 do
      for j := 0 to 2 * n + 1 do
        begin
          if (koord[i].x > koord[j].x) or (koord[i].y > koord[j].y) or
             (i = j) { atgal neisime, taigi ir atstumo neskai‡iuosime }
             then g [i, j] := 200 { fiktyvus atstumas }
             else
               begin { reikia patikrinti, ar dvi virž–nes jungianti }
                     { atkarpa nekerta kit— kvadrat‚li— }
                 kerta := false;
                 for k := 1 to n do
                   if (abs (tiese(i, j, 2*k-1) - tiese(i, j, 2*k)) = 2) and
                      (abs (tiese(2*k-1, 2*k, i) - tiese(2*k-1, 2*k, j)) = 2)
                      then begin
                             g [i, j] := 200; { fiktyvus atstumas }
                             kerta := true;
                           end;
                   { jei viskas tvarkoje, skai‡iuojame atstum… }
                   if not kerta
                      then g[i, j] := sqrt(sqr(koord[i].x - koord[j].x) +
                                           sqr(koord[i].y - koord[j].y));
                  end { else }
        end;
  end;

 procedure Dijkstra;
   { randa trumpiausi… keli… grafe atst nuo nulin‚s iki vis— likusi— }
   { virž–ni— }
   { pradiniai duomenys - n ir g }
   { rezultatas - pi }

   var i, u, v : integer;
       min : real;
       Q : aibe;
       d : atstumai;
 begin
   for i := 0 to 2 * n + 1 do
     begin
       d[i] := maxint;
       pi[i] := 0
     end;
   d[0] := 0;
   Q := [0..2*n+1];
   while Q <> [] do
     begin
       { rasime virž–nŠ, iki kurios atstumas yra trumpiausias }
       min := maxint;
       for i := 0 to 2 * n + 1 do
         if (d[i] < min) and (i in Q)
            then begin
                   u := i;
                   min := d[i]
                 end;
       Q := Q - [u];
       for v := 0 to 2 * n + 1 do
           if d[v] > d[u] + g[u, v]
                    then begin
                           d[v] := d[u] + g[u, v];
                           pi[v] := u;
                         end;
     end;
  end;

  procedure spausdinti;
    { ižveda rezultatus }
    { pradiniai duomeys - n ir pi }
    var f : text;
    procedure spausd (v : integer);
    begin
       if v <> 0
          then spausd (pi[v]);
       writeln (f, koord[v].x, ' ', koord[v].y)
    end;
  begin
    assign (f, 'kelias.rez');
    rewrite (f);
    spausd (2 * n + 1);
    close (f)
  end;

begin
 ivedimas;
 grafo_sudarymas;
 dijkstra;
 spausdinti;
end.



