option=com_onlinejudge&Itemid=8&page=show_problem&category=514&problem=4077&mosmsg=Submission+received+with+ID+13588936">题目链接：uva 1331 - Minimax Triangulation

题目大意：依照顺时针或者逆时针的顺序给出多边的点，要将这个多边形分解成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;

}