Minimax Triangulation UVA - 1331（区间DP，最大三角形最小剖分）

本文主要是介绍Minimax Triangulation UVA - 1331（区间DP，最大三角形最小剖分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

思路：
区间dp。
定义 $d p [i] [j]$ 为处理完了i~j之间的点的答案。
子状态就是 $d p [i] [k]$ ， $d p [k] [j]$ ，或者直接由 $i, j, k$ 组成的三角形。
但是这个多边形不一定是凸包，所以要保证当前组成的三角形不是凹的，方法就是判断是否有点在这个三角形里面。

不过值得注意的是，这个方法不能判断单独三点构成的凹三角形，但这没有影响。因为当区间长度为4或更大的时候，这个凹三角形是无法被统计进来的。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>using namespace std;const int INF = 0x3f3f3f3f;
const int maxn = 55;struct Point {double x,y;Point(){}Point(int x,int y) {this -> x = x;this -> y = y;}friend Point operator - (const Point&a,const Point&b) {return Point(a.x - b.x,a.y - b.y);}friend Point operator + (const Point&a,const Point&b) {return Point(a.x + b.x,a.y + b.y);}friend double operator * (const Point&a,const Point&b) {return a.x * b.y - a.y * b.x;}
}a[maxn];
double dp[maxn][maxn];
int n;bool judge(int x,int y,int z) {for(int i = 1;i <= n;i++) {if(i == x || i == y || i == z) continue;double s1 = fabs((a[i] - a[x]) * (a[i] - a[y])) + fabs((a[i] - a[x]) * (a[i] - a[z])) + fabs((a[i] - a[y]) * (a[i] - a[z]));double s2 = fabs((a[x] - a[y]) * (a[x] - a[z]));if(fabs(s1 - s2) < 1e-8) return true;}return false;
}int main() {int T;scanf("%d",&T);while(T--) {scanf("%d",&n);for(int i = 1;i <= n;i++) {scanf("%lf%lf",&a[i].x,&a[i].y);}memset(dp,0,sizeof(dp));for(int len = 3;len <= n;len++) {for(int i = 1;i + len - 1 <= n;i++) {int j = i + len - 1;dp[i][j] = INF;for(int k = i + 1;k <= j - 1;k++) {if(judge(i,k,j)) continue;dp[i][j] = min(dp[i][j],max(max(dp[i][k],dp[k][j]),fabs((a[i] - a[j]) * (a[i] - a[k])) / 2));}}}printf("%.1f\n",dp[1][n]);}return 0;
}