POJ1696 (Pascal)

poj1696.pas

var
  m,n,i:longint;
  a:array [0..100,0..3] of longint;

function cross_product(p,q,r:longint):longint;
var
  t1,t2,t3,t4:longint;

begin
  t1:=a[q,1]-a[p,1];
  t2:=a[q,2]-a[p,2];
  t3:=a[r,1]-a[p,1];
  t4:=a[r,2]-a[p,2];
  exit(t1*t4-t2*t3);
end;

procedure main;
var
  i,j,min,minj,p,q:longint;
  f:array [0..100] of longint;
  t,mint:longint;

begin
  readln(n);
  min:=1;
  fillchar(f,sizeof(f),0);
  for i:=1 to n do
    begin
      readln(a[i,0],a[i,1],a[i,2]);
      if a[i,2]<a[min,2] then min:=i;
    end;
  a[0,0]:=0;
  a[0,1]:=0;
  a[0,2]:=a[min,2];
  p:=0; q:=min;
  f[p]:=1; f[q]:=1;
  write(n,' ',a[min,0]);
  for i:=1 to n-1 do
    begin
      //vector: a[p]->a[q]
      minj:=1;
      while (f[minj]=1) do inc(minj);
      for j:=1 to n do
        if (f[j]=0) then
          begin
            t:=cross_product(q,minj,j);
            if t<=0 then minj:=j;
          end;
      write(' ',a[minj,0]);
      p:=q; q:=minj;
      f[minj]:=1;
    end;
  writeln;
end;

begin
  readln(m);
  for i:=1 to m do main;
end.