您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

UVA 1331 Minimax Triangulation：區間 DP 多邊形三角剖分

編輯：關於C++

UVA 1331 Minimax Triangulation 詳解

題目：給定凸多邊形 m 個頂點（2 < m < 50），按順序（順/逆時針）給出座標。將其三角剖分為 m-2 個三角形（用 m-3 條不相交對角線）。定義某剖分的「代價」為其中面積最大的三角形面積。求所有合法剖分中，最小可能的最大三角形面積，輸出保留一位小數。

核心模型：區間 DP

頂點編號 0...m-1。定義 dp[i][j] 為頂點 i 到 j（順時針）構成的子多邊形，在最優剖分下的「最大三角形面積的最小值」。
最終答案：dp[0][m-1]。

狀態轉移

對於區間 [i, j]（長度 ≥ 3），枚舉中間頂點 k (i < k < j)，形成三角形 (i, k, j)。若該三角形不包含其他頂點（即為合法剖分三角形），則：

dp[i][j] = min over k { max( area(i,k,j), dp[i][k], dp[k][j] ) }

意義：以 (i,k,j) 為一個三角形，剩餘兩側 [i,k]、[k,j] 遞歸剖分。該剖分下的最大面積為三者最大值。我們在所有合法 k 中取最小的最大值。

合法性判斷：三角形內無其他頂點

三角形 (i,k,j) 合法 ⇔ 其內部不含其他頂點。利用面積法：
設 S = area(i,k,j)。對任意頂點 p ∉ {i,k,j}，若 area(i,k,p) + area(k,j,p) + area(j,i,p) == S（誤差 1e-7），則 p 在三角形內或邊上 → 不合法。
若所有 p 都不在內部，則合法。

遞歸邊界

j == i+1：只有兩個頂點，無法形成三角形，dp[i][j] = 0。
j == i+2：恰好三個頂點，構成一個三角形，dp[i][j] = area(i,i+1,i+2)。

實現細節

頂點數 m ≤ 50，三重循環 O(m³) 完全足夠（~12.5萬次）。
面積計算：叉積公式 area = 0.5 * |(B-A) × (C-A)|。
DP 初始化：-1 表示未計算，遞歸 + 記憶化（或長度遞增迭代）。
輸出：printf("%.1f\n", dp[0][m-1]); 保留一位小數。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;

struct Point { double x, y; };
const double INF = 1e100;
const double EPS = 1e-7;

double area(const Point& a, const Point& b, const Point& c) {
    return fabs((b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y)) * 0.5;
}

int m;
Point pt[55];
double dp[55][55];

double dfs(int l, int r) {
    if (r <= l + 1) return dp[l][r] = 0;
    if (dp[l][r] > -0.5) return dp[l][r]; // 已計算
    double res = INF;
    for (int k = l + 1; k < r; ++k) {
        // 檢查三角形 (l,k,r) 是否合法
        bool ok = true;
        double S = area(pt[l], pt[k], pt[r]);
        for (int i = 0; i < m && ok; ++i) {
            if (i == l || i == k || i == r) continue;
            double sum = area(pt[l], pt[k], pt[i]) 
                       + area(pt[k], pt[r], pt[i]) 
                       + area(pt[r], pt[l], pt[i]);
            if (fabs(sum - S) < EPS) ok = false;
        }
        if (ok) {
            double cur = max(S, max(dfs(l, k), dfs(k, r)));
            res = min(res, cur);
        }
    }
    return dp[l][r] = res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        cin >> m;
        for (int i = 0; i < m; ++i) cin >> pt[i].x >> pt[i].y;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < m; ++j)
                dp[i][j] = -1;
        cout << fixed << setprecision(1) << dfs(0, m-1) << '\n';
    }
    return 0;
}