题意：

看白书

要点：

基本的三角剖分题，但要注意三个点：

1.已知三角形三个顶点的坐标，可用行列式求面积，则S=（1/2)*(下面行列式）

|x1 y1 1|

|x2 y2 1|

|x3 y3 1|

S=(1/2)*(x1y2*1+x2y3*1+x3y1*1-x1y3*1-x2y1*1-x3y2*1)

2.这题没有说多边形一定是凸多边形，所以要考虑凹多边形的情况，拆分时如果拆出的三角形中有其他顶点说明这种情况不合法，判断方式是依照面积，遍历所有点，如果在三角形内部，与其他点形成的三角形面积之和等于这个三角形的面积。

3.题目是求最大三角形的最小值，意思是拆分出的三角形中选最大三角形，而通过不断变动选取的点，使这个最大三角形值最小，所以状态转移方程为：

d[i][j] = min(d[i][j], max(max(d[i][k], d[k][j]), s(i, k, j)))

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define inf 0x3f3f3f3f;using namespace std;struct node{	double x, y;}m[55];double d[55][55];int n;double cal_num(int a, int b, int c){	return fabs(0.5*(m[a].x*(m[b].y - m[c].y) + m[b].x*(m[c].y - m[a].y) + m[c].x*(m[a].y - m[b].y)));}bool check(int a, int b, int c)//判断三角形内部是否有点{	for (int i = 1; i <= n; i++)	{		if (i == a || i == b || i == c)			continue;		double temp = cal_num(i, a, b) + cal_num(i, c, a) + cal_num(i, b, c);		if (fabs(temp - cal_num(a, b, c)) < 1e-6)			return true;	}	return false;}int main(){	int t,i,j,k,l;	scanf("%d", &t);	while (t--)	{		scanf("%d", &n);		for (i = 1; i <= n; i++)			scanf("%lf%lf", &m[i].x, &m[i].y);		memset(d, 0, sizeof(d));		for (l = 2; l < n; l++)		{			for (i = 1; i + l <= n; i++)			{				j = i + l;				d[i][j] = inf;				for (k = i + 1; k < j; k++)				{					if (check(i, k, j))						continue;					d[i][j] = min(d[i][j], max(max(d[i][k], d[k][j]), cal_num(i, k, j)));//注意题目是求最大三角形的最小值				}			}		}		printf("%.1lf\n", d[1][n]);	}	return 0;}