因为存在凹形,因此枚举点的时候注意一下内部是否有点,如果有点则不可分割,其他就是多边形的分割
#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\n", f[1][n]); } return 0; }View Code