NKPOLY - Chia đa giác
Tác giả: ladpro98
Ngôn ngữ: C++
#include <bits/stdc++.h>
#define dd pair<double, double>
#define X first
#define Y second
const int N = 202;
const double oo = 10000000000000.0;
using namespace std;
double F[N][N];
int n;
dd a[N];
double area(dd a, dd b, dd c) {
return fabs(a.X * (b.Y - c.Y) + b.X * (c.Y - a.Y) + c.X * (a.Y - b.Y)) / 2;
}
int main()
{
scanf("%d", &n);
int i, j, k, len; double res1 = 0;
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++) res1 = max(res1, area(a[i], a[j], a[k]));
for(len = 2; len <= n; len++) for(i = 1; i <= n - len; i++) {
j = i + len; F[i][j] = oo;
for(k = i + 1; k < j; k++)
F[i][j] = min(F[i][j], max(max(F[i][k], F[k][j]), area(a[i], a[k], a[j])));
}
printf("%.1lf\n", res1); printf("%.1lf", F[1][n]);
return 0;
}