program keliautojas;
  const MAX_N = 16; { maksimalus miest— skai‡ius + 1 }
  type taskas = record
                  x, y : longint;
                end;
       koordinates = array [1..MAX_N] of taskas;
       atstumai = array [1..MAX_N, 1..MAX_N] of real;
       marsrutas = array [0..MAX_N+1] of longint;


  { ‘emiau suražyti globalieji kintamieji }
  var koord: koordinates; { miest— koordinat‚s }
      n: longint;         { miest— skai‡ius }
      min_kel_ilg, max_kel_ilg: real; { trumpiausio ir ilgiausio
                                        maržrut— ilgiai }
      min_mar, max_mar: marsrutas;  { ilgiausias ir trumpiausias maržrutai }
      atst: atstumai;     { atstumai tarp miest— }

  procedure rask_atstumus (var atst: atstumai);
    { suranda atstumas tarp vis— miest— }
    var i, j: longint;
  begin { rask_atstumus }
    for i := 1 to n do
      for j := i + 1 to n do
        begin
          atst[i, j] := sqrt (sqr (koord[i].x - koord[j].x) +
                               sqr (koord[i].y - koord[j].y));
          atst[j, i] := atst[i, j];
        end;
  end; { rask_atstumus }

  function min_max (x, y: longint; minim: boolean): longint;
    { randa didesnŤjŤ arba ma‘esnŤnŤ iž dviej— skai‡i— }
  begin
    if (x < y) and minim or (x > y) and not minim
       then min_max := x
       else min_max := y;
  end; { min_max }

  function priklauso (A, B, C: taskas): boolean;
    { ar tažkas C priklauso atkarpai AB }
    var prik_tiesei: boolean;
  begin
    { ar tažkas C priklauso tiesei einan‡iai per tažkus A ir B }
    prik_tiesei := (C.x - A.x)*(B.y - A.y) = (C.y - A.y)*(B.x - A.x);
    { ar tažkas C priklauso atkarpai }
    priklauso := (C.x >= min_max (A.x, B.x, true)) and
                 (C.x <= min_max (A.x, B.x, false)) and
                 (C.y >= min_max (A.y, B.y, true)) and
                 (C.y <= min_max (A.y, B.y, false)) and prik_tiesei
  end; { kerta }

  procedure patikrink (mars: marsrutas;
                       keli: integer; { keli miestai Ťeina Ť maržrut… }
                       var kel_ilg: real; { maržruto ilgis }
                       var tinka: boolean { ar tinkamas });
   { randa maržruto ilgŤ ir patikrina, ar jis neturi susikirtim— }
    var i, j: longint;
        norm, aibe: set of 0..255;
  begin { patikrink }
    { pabaigus kelionŠ grŤ‘tama Ť t… patŤ miest… }
    mars[keli+1] := mars[1];
    mars[0] := mars[keli];
    { rasime kelio ilgŤ }
    kel_ilg := atst[mars[keli+1], mars[1]];
    for i := 1 to keli do
      kel_ilg := kel_ilg + atst[mars[i], mars[i+1]];
    { rasime visus miestus, kurie aplankomi netiesiogiai }
    aibe := []; tinka := true;
    for i := 1 to n do { ar tažkas  }
      for j := 1 to keli do { priklauso atkarpai }
       if (i <> mars[j]) and (i <> mars[j+1]) and
          priklauso (koord[mars[j]], koord[mars[j+1]], koord[i])
          then if i in aibe
                  then tinka := false
                  else aibe := aibe + [i];
    { randame normaliai aplankytus miestus }
    norm := [];
    for i := 1 to keli do
      if (mars[i] in norm) and (mars[i] <> mars[i-1])
         then tinka := false
         else norm := norm + [mars[i]];
    { ar miestas n‚ra aplankomas du kartus }
    tinka := tinka and (norm * aibe = []);
    { ar visi miestai aplankomi }
    tinka := tinka and (norm+aibe = [1..n]);
  end; { patikrink }

  procedure naujas_marsrutas;
    { perskaito nauj… maržrut… ir jŤ pakomentuoja }
    var tinka: boolean;
        i, num, keli: longint;
        kel_ilg: real;
        mars: marsrutas;
  begin { naujas_maržrutas }
    writeln ('­veskite miest— numerius ta tvarka, kuria norite juos');
    writeln ('aplankyti. Maržruto pabaig… ‘ym‚kite 0:');
    write ('> ');
    { perskaitomas maržrutas }
    keli := 0;
    repeat
      keli := keli + 1;
      read (mars[keli]);
    until mars[keli] = 0;
    keli := keli - 1;
    readln;
    { patikrinama, ar aplankomis visi miestai ir
      ar per jokŤ miest… neinama du kartus }
    patikrink (mars, keli, kel_ilg, tinka);
    writeln ('A‡i–. Kelio ilgis - ', kel_ilg: 0: 2, ' km.');
    if tinka
       then writeln ('Maržrutas geras.')
       else writeln ('Maržrutas netinkamas.');
    { gal radome ilgesnŤ arba trumpesnŤ maržrut… }
    if tinka and (kel_ilg <= min_kel_ilg)
       then begin
              min_kel_ilg := kel_ilg;
              min_mar := mars;
            end;
    if tinka and (kel_ilg >= max_kel_ilg)
       then begin
              max_kel_ilg := kel_ilg;
              max_mar := mars;
            end;
  end; { naujas_maržrutas }

  var i: longint;
      toliau: char;

begin
  { dialogo prad‘ia: Ťvedamos miest— koordinat‚s }
  writeln ('Sveiki!');
  writeln ('Kiek daugiausia skirting— miest— gali Ťeiti Ť maržrut…?');
  write ('> ');
  readln (n);
  writeln ('­veskite ži— miest— koordinates (x, y):');
  for i := 1 to n do
    begin
      write (i, ' miestas> ');
      readln (koord[i].x, koord[i].y);
    end;
  writeln ('A‡i–.');
  { randami atstumai tarp miest— }
  rask_atstumus (atst);
  { kol kas nerastas nei trumpiausias nei ilgiausias kelias }
  min_kel_ilg := maxlongint;
  max_kel_ilg := 0;
  { Ťvesime visus maržrutus }
  writeln ('­veskite J–s— pasirinktus maržrutus.');
  repeat
    naujas_marsrutas;
    writeln ('Dar bandysite? (t/n)');
    write ('> ');
    readln (toliau);
  until toliau = 'n';
  { pasi–lomi maržutai }
  if max_kel_ilg = 0
     then writeln ('J–s neŤved‚te nei vieno teisingo maržruto.')
     else begin
            writeln ('Si–lytume tokius maržrutus:');
            write   ('    trumpiausi… - ');
          for i := 1 to n do
            write (min_mar[i], ' ');
          writeln ('(ilgis - ', min_kel_ilg: 0: 2, ' km);');
          write ('      ilgiausi… - ');
          for i := 1 to n do
            write (max_mar[i], ' ');
          writeln ('(ilgis - ', max_kel_ilg: 0: 2, ' km).');
          writeln ('Laimingo kelio!');
        end
end.