题目大意：依照顺时针或者逆时针的顺序给出多边的点，要将这个多边形分解成n-2个三角形，要求使得这些三角行中面积最大的三角形面积尽量小，求最小值。
解题思路：状态非常好想。dp[i][j]表示从第i个点到第j个点，划分成j-i-1个三角形的最优解，然后每次转移时，枚举长度和左边界始点，那么依据长度和左边界点就能够知道右边界点。然后枚举左边界和右边界中间的点k。dp[i][j] = min(dp[i][j], max(max(dp[i][k], dp[k][j]), Area(i, k, j)).可是有一个问题，即i，k，j三点围成的三角形是否符合要求，推断的条件即为是否存在除i。k。j三点外的一点位于三角形中，有面积法推断。
然后事实上我还一直纠结说凹多边形的时候怎么处理掉得，如图
BCD的组成的三角形式合法的，可是后来想了想。尽管BCD组成的三角形是合法的，可是不会影响到最后的答案。
。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm> using namespace std;
const int N = 100;
const double INF = 0x3f3f3f3f3f3f;
const double eps = 1e-9; struct point {
double x, y;
void get() {
scanf("%lf%lf", &x, &y);
}
}p[N]; int n;
double dp[N][N]; double area (point a, point b, point c) {
return fabs((b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y))/2;
} bool judge (int a, int b, int c) {
double cur = area(p[a], p[b], p[c]);
for (int i = 0; i < n; i++) {
if (i == a || i == b || i == c)
continue;
double tmp = area(p[a], p[b], p[i]) + area(p[b], p[c], p[i]) + area(p[c], p[a], p[i]);
if (fabs(tmp - cur) < eps)
return false;
}
return true;
} double solve () {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < n; j++)
dp[j][(j+i)%n] = 0;
} for (int i = 0; i < n; i++)
dp[i][(i+2)%n] = area(p[i], p[(i+1)%n], p[(i+2)%n]); for (int k = 3; k < n; k++) { for (int i = 0; i < n; i++) {
int t = (i + k) % n;
dp[i][t] = INF;
for (int j = (i+1)%n; j != t; j = (j+1)%n) {
if (judge(i, t, j))
dp[i][t] = min(dp[i][t], max(max(dp[i][j], dp[j][t]), area(p[i], p[j], p[t])));
}
}
} double ans = INF;
for (int i = 0; i < n; i++)
ans = min (ans, dp[i][(i+n-1)%n]);
return ans;
} int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
scanf("%d", &n);
for (int i = 0; i < n; i++)
p[i].get(); printf("%.1lf\n", solve());
}
return 0;
}
版权声明：本文博主原创文章，博客，未经同意不得转载。