NKPOLY - Chia đa giác
Tác giả: RR
Ngôn ngữ: Pascal
{$R-,Q-}
uses math;
const
FINP='';
FOUT='';
MAXN=200;
var
f1,f2:text;
s:array[1..MAXN,1..MAXN,1..MAXN] of double;
d:array[1..MAXN,1..MAXN] of double;
x,y:array[1..MAXN] of double;
n:longint;
procedure openF; inline;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF; inline;
begin
close(f1); close(f2);
end;
procedure inp; inline;
var
i:longint;
begin
read(f1,n);
for i:=1 to n do
read(f1,x[i],y[i]);
end;
procedure solve;
var
i,j,k,c:longint;
kq:double;
begin
kq:=0;
for i:=1 to n-2 do
for j:=i+1 to n-1 do
for k:=j+1 to n do
begin
s[i,j,k]:=abs(x[i]*y[j]-y[i]*x[j]+x[j]*y[k]-y[j]*x[k]+x[k]*y[i]-x[i]*y[k]);
kq:=max(kq,s[i,j,k]);
end;
writeln(f2,kq/2:0:1);
for k:=2 to n-1 do
for i:=1 to n-k do
begin
j:=i+k; d[i,j]:=4e12;
for c:=i+1 to j-1 do
d[i,j]:=min(d[i,j],max(max(d[i,c],d[c,j]),s[i,c,j]));
end;
writeln(f2,d[1,n]/2:0:1);
end;
begin
openF;
inp;
solve;
closeF;
end.