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.

Download