NKPOLI - Đa giác

Tác giả: flashmt

Ngôn ngữ: Pascal

uses math;
const maxn=100;
var n,re,i,j,k:longint;
    x,y:array[1..maxn] of longint;
    f:array[1..maxn,1..maxn] of longint;

function check(i,j,k:longint):boolean;
begin
     check:=(x[i]-x[j])*(y[i]+y[j])+(x[j]-x[k])*(y[j]+y[k])+(x[k]-x[i])*(y[i]+y[k])<0;
end;

begin
     read(n);
     for i:=1 to n do read(x[i],y[i]);
     for i:=1 to n-1 do
         for j:=i+1 to n do
             if y[i]*x[j]>y[j]*x[i] then
             begin
                  k:=x[i]; x[i]:=x[j]; x[j]:=k;
                  k:=y[i]; y[i]:=y[j]; y[j]:=k;
             end;
     for i:=2 to n do
         for j:=1 to i-1 do
         begin
              f[i,j]:=3;
              for k:=1 to j-1 do
                  if check(i,j,k) then
                     f[i,j]:=max(f[i,j],f[j,k]+1);
         end;
     re:=3;
     for i:=2 to n do
         for j:=1 to i-1 do
             re:=max(re,f[i,j]);
     writeln(re);
end.

Download