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.