把一个多边形剖分成若干个三角形，使得其中最大的三角形面积最小。
比较经典的一道dp问题
设dp[l][r]为把多边形[l,r]剖分成三角形的最大三角形面积中的最小值，则$dp[l][r]=min\{dp[l][i]+dp[i][r]+area(l,i,r)\}$
注意：
1.由于多边形的点不一定按顺时针或者逆时针排列，需要按点的顺序计算一遍多边形的面积，如果为负说明是顺时针排列，需要反转一下。
2.进行剖分的时候有可能会“出界”，但无需进行线段相交判断，只需在计算的面积出现负数时返回inf即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N=+;
const db inf=1e18;
struct P {
db x,y;
P operator-(P& b) {return {x-b.x,y-b.y};}
} p[N];
db cross(P a,P b) {return a.x*b.y-a.y*b.x;}
int n;
db calarea() {
db ret=;
for(int i=; i<n-; ++i)ret+=cross(p[i]-p[],p[i+]-p[]);
return ret/;
}
db calarea(int l,int m,int r) {
return cross(p[l]-p[r],p[m]-p[r])/;
}
db d[N][N];
db dp(int l,int r) {
if(r-l<)return ;
db& ret=d[l][r];
if(ret>=)return ret;
ret=inf;
for(int i=l+; i<r; ++i) {
db area=calarea(l,i,r);
if(area>)ret=min(ret,max(dp(l,i),max(dp(i,r),area)));
}
return ret;
} int main() {
int T;
for(scanf("%d",&T); T--;) {
scanf("%d",&n);
for(int i=; i<n; ++i)scanf("%lf%lf",&p[i].x,&p[i].y);
if(calarea()<)reverse(p,p+n);
memset(d,,sizeof d);
printf("%.1f\n",dp(,n-));
}
return ;
}