NKPOLY - Chia đa giác
Tác giả: hieult
Ngôn ngữ: C++
#include <cstdio>
#include <iostream>
//#include <conio.h>
struct point
{ double x,y; };
point A[210];
int n;
double f[210][210];
double TTD(double x) { return x>0 ? x:-x ;}
double area(int i, int j, int k)
{
return TTD(((A[i].x*A[j].y-A[j].x*A[i].y)+(A[j].x*A[k].y-A[k].x*A[j].y)+(A[k].x*A[i].y-A[i].x*A[k].y))/2);}
double max(double a,double b,double c)
{
if(a>b && a>c) return a;
if(b>c && b>a) return b; return c; }
int main()
{
//freopen("NKPOLY.in","r",stdin);
scanf("%d",&n);
double KQmax =0 ,rich,u=100000000,v=100000000;
int i,j,t,hieu,k;
for(i = 1;i<=n;i++)
scanf("%lf %lf",&A[i].x,&A[i].y);
for(i = 1;i<=n;i++)
for(j = i+1;j<=n;j++)
for(k = j+1;k<=n;k++)
{
rich = area(i,j,k);
if(rich>KQmax)
KQmax = rich;
}
for(i = 1;i<=n-1;i++) {f[i][i] = 0; f[i][i+1] = 0;}
f[n][n] = 0;f[n][1]=0;
for(hieu = 2;hieu<=n-1;hieu++)
{
for(i = 1;i<=n;i++)
{
j = (i+hieu-1)%n+1;
f[i][j] = u*v;
if(j>i)
{
for(t = i+1;t<j;t++)
{
rich = max(f[i][t],f[t][j],area(i,t,j));
if(f[i][j]>rich)
f[i][j] = rich;
}
}
else
{
for(t = i+1;t<=n;t++)
{
rich = max(f[i][t],f[t][j],area(i,t,j));
if(f[i][j]>rich)
f[i][j] = rich;
}
for(t = 1;t<j;t++)
{
rich = max(f[i][t],f[t][j],area(i,t,j));
if(f[i][j]>rich)
f[i][j] = rich;
}
}
}
}
printf("%.1lf\n%.1lf\n",KQmax,f[2][1]);
// getch();
}