UVA 609 Metal Cutting：凸多邊形最小切割長度

問題描述

給定一個 n×m 的矩形金屬板，需從中切出一個凸多邊形（≤8 頂點）。切割機只能沿直線完全切穿。求切出多邊形所需的最小總切割長度。切割必須沿多邊形邊緣進行。

核心觀察

• 每次切割將當前區域分為兩部分，保留包含目標多邊形的部分。
• 切割順序影響總長度：先切長邊可能讓後續切變短。
• 最多 8 條邊 → 8! = 40320 種順序，可暴力枚舉排列。

算法流程

1. 將矩形四邊初始化為初始切割線集合。
2. 枚舉多邊形邊的所有排列（next_permutation）。
3. 對每種順序模擬切割：
1. 當前切割線與已有線集合求交點。
2. 在切割線上找到位於當前保留區域邊界上的兩個交點，距離即為本次切割長度。
3. 將該切割線加入集合，繼續下一條。
4. 取所有排列中的最小總長度。

幾何關鍵函數

// 判斷兩線是否平行
bool parallel(Line a, Line b) {
    return fabs(cross(a.b-a.a, b.b-b.a)) < EPS;
}

// 求兩線交點
Point intersection(Line a, Line b) {
    // 解線性方程組
    double d = cross(a.b-a.a, b.b-b.a);
    return a.a + (a.b-a.a) * cross(b.a-a.a, b.b-b.a) / d;
}

// 判斷點 c 是否在向量 ab 的左側（或共線）
bool outside(Point a, Point b, Point c) {
    return dot(c-a, b-a) > EPS;
}

// 計算切割線在當前多邊形上的切割長度
double cut_length(Line L, vector& current) {
    Point p1, p2; // 兩個有效交點
    double min1 = INF, min2 = INF;
    for (Line& e : current) {
        if (parallel(L, e)) continue;
        Point ip = intersection(L, e);
        double d1 = dist(L.a, ip), d2 = dist(L.b, ip);
        if (outside(L.b, L.a, ip) && d1 < min1) { min1 = d1; p1 = ip; }
        if (outside(L.a, L.b, ip) && d2 < min2) { min2 = d2; p2 = ip; }
    }
    return dist(p1, p2);
}

複雜度分析

• 排列數：P ≤ 8! = 40320。
• 單次模擬：O(P × 當前邊數) ≤ O(8×12)。
• 總體：極快，輕鬆通過。

總結

本題結合了幾何計算（線段相交、點線關係）與排列枚舉。關鍵在於正確維護「當前保留區域的邊界線集合」，並精確計算每次切割在當前邊界上的實際長度。適合作為計算幾何入門綜合練習。