fork download
copy 
  1.  
  2. const md=1 shl 22-1;
  3. type tt=record
  4.  x,y:int64;
  5. end;
  6. type ttt=record
  7.  x,y,id1,id2:longint;
  8. end;
  9. Var ot:array[0..1500,1..3]of longint;
  10.     p,list:array[0..1533]of tt;
  11.     id1,id2,i,j,n,num,u,k,l,r:longint;
  12.     ok:boolean;
  13.     x,y:int64;
  14.     last:array[0..md+1]of longint;
  15.     next:array[0..1500*1503]of longint;
  16.     a:array[0..1500*1503]of ttt;
  17.     used:array[0..1533]of boolean;
  18.     number:array[0..1533]of longint;
  19.  procedure add(x,y,num1,num2:longint);
  20.    var h:int64;
  21.      begin
  22.        h:=(int64(x)*int64(y))and md;
  23.        inc(k);
  24.        next[k]:=last[h];
  25.        last[h]:=k;
  26.        a[k].x:=x;
  27.        a[k].y:=y;
  28.        a[k].id1:=num1;
  29.        a[k].id2:=num2;
  30.      end;
  31.  procedure get(x,y:longint;var id1,id2:longint);
  32.    var h:int64;
  33.        j:longint;
  34.      begin
  35.        id1:=-1;
  36.        h:=(int64(x)*int64(y))and md;
  37.        j:=last[h];
  38.        while j>0 do
  39.          begin
  40.            if (a[j].x=x)and(a[j].y=y) then
  41.              begin
  42.                id1:=a[j].id1;
  43.                id2:=a[j].id2;
  44.                exit;
  45.              end;
  46.            j:=next[j];
  47.          end;
  48.      end;
  49.  function gcd(x,y:int64):int64;
  50.    begin
  51.      while (x>0)and(y>0) do
  52.        if x>y then x:=x mod y
  53.        else y:=y mod x;
  54.      gcd:=x+y;
  55.    end;
  56.  procedure getmid(x1,y1,x2,y2:int64;var x,y:int64);
  57.    var d:int64;
  58.      begin
  59.      //  Writeln(x1,' ',y1,' ',x2,' ',y2);
  60.        d:=(y1*y2) div gcd(y1,y2);
  61.        x1:=x1*(d div y1);
  62.        x2:=x2*(d div y2);
  63.        x:=x1+x2;
  64.        y:=d+d;
  65.        d:=gcd(x,y);
  66.        x:=x div d;
  67.        y:=y div d;
  68.      end;
  69.   begin
  70.     assign(input,'points.in');
  71.     reset(input);
  72.     assign(output,'points.out');
  73.     rewrite(output);
  74.     read(n);
  75.     for i:=1 to n do
  76.      begin
  77.       read(p[i].x,p[i].y);
  78.       if p[i].x=0 then l:=i;
  79.       if (p[i].x=1)and(p[i].y=1) then r:=i;
  80.      end;
  81.     add(1,2,l,r);
  82.     fillchar(used,sizeof(used),false);
  83.     used[l]:=true;
  84.     used[r]:=true;
  85.     list[1]:=p[l];
  86.     list[2]:=p[r];
  87.     number[1]:=l;
  88.     number[2]:=r;
  89.     for i:=1 to n-2 do
  90.       begin
  91.         ok:=false;
  92.         for j:=1 to n do
  93.           if not used[j] then
  94.             begin
  95.               num:=j;
  96.               get(p[j].x,p[j].y,id1,id2);
  97.               if id1=-1 then continue;
  98.               ok:=true;
  99.               ot[i,1]:=j;
  100.               ot[i,2]:=id1;
  101.               ot[i,3]:=id2;
  102.               list[i+2]:=p[j];
  103.               number[i+2]:=j;
  104.               used[j]:=true;
  105.               for u:=1 to i+1 do
  106.                 begin
  107.  
  108.                   getmid(list[u].x,list[u].y,p[j].x,p[j].y,x,y);
  109.                   if y>1000000000 then continue;
  110.                   add(x,y,number[u],j);
  111.                 end;
  112.               break;
  113.             end;
  114.         if not ok then begin Writeln('NO');Writeln(num);halt(0);end;
  115.       end;
  116.      Writeln('YES');
  117.      for i:=1 to n-2 do
  118.        Writeln(ot[i,1],' ',ot[i,2],' ',ot[i,3]);
  119.   end.
Runtime error #stdin #stdout 0.01s 60704KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Runtime error 2 at $0804844A
  $0804844A
  $0805F6B1
https://ideone.com/11A7QE
language:
Pascal (fpc 3.0.4)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!