NC15031 小仙女过生日（区间dp）

因为存在凹形，因此枚举点的时候注意一下内部是否有点，如果有点则不可分割，其他就是多边形的分割

#include <bits/stdc++.h>
#define LL long long
using namespace std;
double f[105][105];
struct point{ 
    double x, y;
}a[105];
double calc(point a,point b,point c){
    return fabs((a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y))/2;
}
 
int ok(int l, int r, int k, int n){
    double s=calc(a[l], a[r], a[k]);
    for(int i=1; i<=n; i++){
        if(i==l||i==r||i==k){
            continue;
        }
        double s1=calc(a[l], a[r], a[i])+calc(a[l], a[k], a[i])+calc(a[k], a[r], a[i]);
        if(fabs(s1-s)<1e-8){
            return 0;
        }
    }
    return 1;
}
 
int main(){
    int n;
    while(~scanf("%d", &n)){
        for(int i=1; i<=n; i++){
            scanf("%lf%lf", &a[i].x, &a[i].y);
        }
        for(int i=1; i<=n-2; i++){
            f[i][i+2]=calc(a[i], a[i+1], a[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(ok(l, r, k, n)){
                        f[l][r]=min(f[l][r], max(max(f[l][k], f[k][r]), calc(a[l], a[r], a[k])));
                    }
                }
            }
        }
        printf("%.1f
", f[1][n]);
    }
 
    return 0;
}