文章目录

• • • • [Minimax Triangulation【典中典题目】](https://vjudge.ppsucxtt.cn/problem/UVA-1331)
      • [Zoj 3537 Cake](https://zoj.pintia.cn/problem-sets/91827364500/problems/91827368971)
      • [hdu6603 Azshara's deep sea (计算几何+区间DP)](https://blog.csdn.net/Sarah_Wang0220/article/details/99198601)

---

Minimax Triangulation【典中典题目】

题解：【动态规划】UVa 1331 最大面积最小三角形剖分

补充：

• 个人理解：对于凹多边形，要判断三角形是否为合法剖分三角形。其中判断三角形是否为合法剖分三角形，要保证三角形内部没有其他点，以及三角形与其他边没有交点（端点处除外）。但是网上都说判断三角形内部是否有其他点即可。代码不知如何实现。

AC代码（数据水）：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
using namespace std;

typedef long long LL;
const int N=110;
const double eps = 1e-9;
const double inf = 9e18;

int dcmp(double x, double y){
    if(fabs(x - y) < eps) return 0;
    if(x < y) return -1;
    return 1;
}
int sign(double x){
    if(fabs(x) < eps) return 0;
    if(x < 0) return -1;
    return 1;
}

struct point{
    double x, y;
};
point operator + (point a, point b) { return {a.x + b.x, a.y + b.y}; }
point operator - (point a, point b) { return {a.x - b.x, a.y - b.y}; }
point operator * (point a, double b) { return {a.x * b, a.y * b}; }
point operator / (point a, double b) { return {a.x / b, a.y / b}; }

double cross(point a, point b) { return a.x * b.y - a.y * b.x; }
double dot(point a, point b) { return a.x * b.x + a.y * b.y; }
double area(point a, point b, point c) { return cross(b - a, c - a) / 2; }

bool segment_intersection(point a1, point a2, point b1, point b2)
{
    if(sign(dot(a2 - a1, b2 - b1)) == 0) return 0;
    double c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1);
    double c3 = cross(b2 - b1, a2 - b1), c4 = cross(b2 - b1, a1 - b1);
    return sign(c1) * sign(c2) < 0 && sign(c3) * sign(c4) < 0;
}

point P[N];
double dp[N][N];
int n;

bool check(int a, int b)
{
    for(int i=1; i<=n; i++)
    {
        if(segment_intersection(P[a], P[b], P[i], P[i % n + 1])) return 0;
    }
    return 1;
}
bool check(int a, int b, int c)
{
    for(int i=1; i<=n; i++)
        if(i != a && i != b && i != c)
        {
            map<int, int>mp;
            mp[sign(area(P[a], P[c], P[i]))] = 1;
            mp[sign(area(P[c], P[b], P[i]))] = 1;
            mp[sign(area(P[b], P[a], P[i]))] = 1;
            if(mp.size() == 1) return 0;
        }
    return 1;
}

int main()
{
    int T; scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        for(int i=1; i<=n; i++) scanf("%lf %lf", &P[i].x, &P[i].y);

        for(int len = 2; len <= n - 1; len++)
            for(int i = 1; i + len <= n; i++)
            {
                int j = i + len;
                dp[i][j] = 1e18;
                for(int k = i + 1; k <j; k++)
                    if(check(i, j, k))
                        dp[i][j] = min(dp[i][j], max(fabs(area(P[i], P[j], P[k])), max(dp[i][k], dp[k][j])));
            }
        printf("%.1f\n", dp[1][n]);
    }

    system("pause");
    return 0;
}

---

Zoj 3537 Cake

题解：Zoj 3537 Cake (DP_最优三角形剖分)

核心代码：

for(int len = 3; len <= n - 1; len++)
    for(int i=1; i + len <= n; i++)
        {
            int j = i + len;
            dp[i][j] = 1e18;
            for(int k = i + 1; k<j; k++)
            {
                double res = dp[i][k] + dp[k][j];
                if(i != k - 1) res += getw(i, k);
                if(j != k + 1) res += getw(j, k);
                dp[i][j] = min(dp[i][j], res);
    		}
        }
printf("%.0f\n", dp[1][n]);

---

hdu6603 Azshara’s deep sea (计算几何+区间DP)

未写。