NKPOLI - Đa giác

Tác giả: RR

Ngôn ngữ: Pascal

program NKPOLI;
uses
  math;
const
  FINP='';
  FOUT='';
  MAXN=101;
  eps=1e-9;
var
  x,y:array[0..MAXN] of longint;
  c:array[0..MAXN] of real;
  d:array[0..MAXN,0..MAXN] of longint;
  n:longint;
procedure inp;
var
  f:text;
  i:longint;
begin
  assign(f,FINP); reset(f);
  readln(f,n);
  x[0]:=0; y[0]:=0;
  for i:=1 to n do
  begin
    readln(f,x[i],y[i]);
    c[i]:=y[i]/x[i];
  end;
  close(f);
end;
procedure ans;
var
  f:text;
  kq,i,j:longint;
begin
  assign(f,FOUT); rewrite(f);
  kq:=0;
  for i:=1 to n do
    for j:=1 to n do
      kq:=max(kq,d[i,j]);
  writeln(f,kq);
  close(f);
end;
procedure swapr(var a,b:real);
var
  temp:real;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure swap(var a,b:longint);
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure sort(l,r:longint);
var
  i,j:longint;
  mid:real;
begin
  mid:=c[(l+r) div 2]; i:=l; j:=r;
  repeat
    while c[i]<mid do inc(i);
    while c[j]>mid do dec(j);
    if i<=j then
      begin
        swapr(c[i],c[j]);
        swap(x[i],x[j]);
        swap(y[i],y[j]);
        inc(i); dec(j);
      end;
  until i>j;
  if i<r then sort(i,r);
  if l<j then sort(l,j);
end;
function CCW(x1,y1,x2,y2,x3,y3:longint):integer;
var
  a1,b1,a2,b2:longint;
  t:real;
begin
  a1:=x2-x1;
  b1:=y2-y1;
  a2:=x3-x2;
  b2:=y3-y2;
  t:=a1*b2-a2*b1;
  if abs(t)<eps then CCW:=0
  else if t<0 then CCW:=-1
  else CCW:=1;
end;
procedure solve;
var
  i,j,k:longint;
begin
  for i:=1 to n do d[0,i]:=2;
  for i:=1 to n-1 do
  for j:=i+1 to n do
    for k:=0 to i-1 do
    if CCW(x[i],y[i],x[j],y[j],x[k],y[k])=1 then
      d[i,j]:=max(d[i,j],d[k,i]+1);
end;
begin
  inp;
  sort(1,n);
  solve;
  ans;
end.

Download