QBPOINT - Bộ ba điểm thẳng hàng

Tác giả: RR

Ngôn ngữ: Pascal

//Wishing myself a happy lunar new year with a lot of accept solutions
{$R+,Q+}
const
  FINP='';
  FOUT='';
  eps=1e-10;
  oo=1000000;
  MAXN=2000;
var
  x,y:array[1..MAXN] of longint;
  tan:array[1..MAXN] of double;
  n,sl,kq:longint;
procedure inp; inline;
var
  f:text;
  i:longint;
begin
  assign(f,FINP); reset(f);
  read(f,n);
  for i:=1 to n do read(f,x[i],y[i]);
  close(f);
end;
procedure swap(var a,b:double); inline;
var
  temp:double;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure sort(l,r:longint); inline;
var
  i,j:longint;
  mid,tg:double;
begin
  i:=l; j:=r; mid:=tan[(l+r) div 2];
  repeat
    while (tan[i]<mid) do inc(i);
    while (tan[j]>mid) do dec(j);
    if i<=j then
      begin
        swap(tan[i],tan[j]);
        inc(i); dec(j);
      end;
  until i>j;
  if l<j then sort(l,j);
  if i<r then sort(i,r);
end;
procedure find(u:longint); inline;
var
  v,i,count:longint;
begin
  sl:=0;
  for v:=u+1 to n do
    begin
      inc(sl);
      if (x[u]=x[v]) then tan[sl]:=oo
      else if (y[u]=y[v]) then tan[sl]:=0
      else tan[sl]:=(y[v]-y[u])/(x[v]-x[u]);
   end;
  if sl=0 then exit;
  sort(1,sl);
  count:=1;
  for i:=2 to sl do
   begin
    if abs(tan[i]-tan[i-1])<eps then inc(count)
    else
      begin
        kq:=kq+(count*(count-1)) shr 1;
        count:=1;
      end;
   end;
  kq:=kq+(count*(count-1)) shr 1;
end;
procedure solve; inline;
var
  i,j:longint;
begin
  kq:=0;
  for i:=1 to n do find(i);
end;
procedure ans; inline;
var
  f:text;
begin
  assign(f,FOUT); rewrite(f);
  writeln(f,kq);
  close(f);
end;
begin
  inp;
  solve;
  ans;
end.

Download