每日一题 6月17日 小仙女过生日啦 凹多边形+三角剖分

题目链接：https://ac.nowcoder.com/acm/problem/15031
题目大意：

思路：除了可能是凹多边形外，就是裸的三角剖分。f[i][j]编号为i，i+1, i+2, ... j的点形成的多边形的最优三角剖分。因为i-j这条边为底，一定属于一个三角形，我们枚举k为顶点进行转移就可以了。
f[l][r]=min(f[l][r], max(max(f[l][k], f[k][r]), calc(a[l], a[r], a[k])));
如果是凹边形，可能出现一个情况。

f[2][7],k=5时。内部有点。那么这个点和2，7，5的连线形成3个三个三角形的面积和为s(2, 7, 4)。我们枚举这个内部点，如果没有就可以剖分。

#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)){
                        //cout<<l<<"-"<<k<<"="<<f[l][k]<<"|"<<k<<"-"<<r<<"="<<f[k][r]<<endl;
                        f[l][r]=min(f[l][r], max(max(f[l][k], f[k][r]), calc(a[l], a[r], a[k])));
                    }
                }
            }
        }
        printf("%.1f\n", f[1][n]);
    }

    return 0;
}