solution

如果给出的是一个凸多边形，那么问题其实就是三角剖分，用不相交的对角线将多边形划分为多个三角形，要求最大的三角形面积最小。求这个面积。

用表示从第个点到第个点进行三角剖分的答案。

转移就枚举一个 满足，

表示以这三个点为顶点的三角形的面积，这个可以直接用叉积计算。

如果给出的不是凸多边形，转移的时候就要检查一下组成的三角形内部是否有点。这个检查就枚举一个点看一看是不是在内部就行了。判断是否在三角形内部就看与三角形的三条边组成的三角形面积之和是否与原三角形面积相等。

关于叉积：向量与向量的叉积。显然这个东西除以2就是向量和向量组成的三角形的面积。

code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<ctime>
#include<set>
using namespace std;
typedef long long ll;
const int N = 110;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
double x[N],y[N];

double calc(int i,int j,int k) {
    return fabs((x[j] - x[i]) * (y[k] - y[i]) - (x[k] - x[i]) * (y[j] - y[i])) / 2;
}

double f[N][N];
int n;
bool pd(int t1,int t2,int t3) {
    double tmp = calc(t1,t2,t3);
    for(int i = 1;i <= n;++i) {
        if(i == t1 || i == t2 || i == t3) continue;
        double t = calc(i,t1,t2) + calc(i,t2,t3) + calc(i,t1,t3);
        if(fabs(tmp - t) <= 1e-8) return false;
    }
    return true;
}

int main() {
    while(cin>>n) {
        for(int i = 1;i <= n;++i) x[i] = read(),y[i] = read();
        for(int i = 1;i + 2 <= n;++i)
            f[i][i + 2] = calc(i,i + 1,i + 2);

        for(int len = 4;len <= n;++len) {
            for(int l = 1;l + len - 1 <= n;++l) {
                int r = l + len - 1;
                f[l][r] = 0x3f3f3f3f;
                for(int k = l + 1;k < r;++k) {
                    if(pd(l,k,r)) {
                        f[l][r] = min(f[l][r],max(f[l][k],max(f[k][r],calc(l,k,r))));
                    }
                }
            }
        }
        printf("%.1lf\n",f[1][n]);
    }
    return 0;
}