UVA 609 Metal Cutting：暴力枚舉切割順序求最小總長度

題目

矩形板 r×l，給定 n (≤8) 個頂點（順時針），需沿多邊形邊切割。枚舉所有切割順序（n!），每次切割長度為當前板上該切割線段在現有板塊上的交集長度。求最小總切割長度。

核心幾何與枚舉

• 預先計算所有切割線（多邊形邊）的直線方程 Ax+By+C=0。
• 維護已切割線段集合（含矩形邊界）。
• 枚舉順序 next_permutation。
• 對於當前切割線，與所有已有線段求交點，篩選落在切割線段兩端點之間的交點，任意兩交點距離即為切割長度，取最小者（因線段可能被分成多段，只需切割包含目標邊的那一段）。

關鍵函數

bool onSegment(Point a, Point b, Point p) { // p 在線段 ab 上
    return min(a.x,b.x) <= p.x && p.x <= max(a.x,b.x) &&
           min(a.y,b.y) <= p.y && p.y <= max(a.y,b.y) &&
           cross(b-a, p-a) == 0;
}
double cutLength(Line L, vector& existing) {
    vector pts = {L.p1, L.p2};
    for (auto &e : existing) {
        if (parallel(L, e)) continue;
        Point ip = intersection(L, e);
        if (onSegment(L.p1, L.p2, ip)) pts.push_back(ip);
    }
    sort(pts.begin(), pts.end(), [&](Point a, Point b){
        return hypot(a.x-L.p1.x, a.y-L.p1.y) < hypot(b.x-L.p1.x, b.y-L.p1.y);
    });
    double minLen = INF;
    for (int i=1; i

struct Line { Point p1,p2; double A,B,C; int id; };
double solve() {
    sort(lines, lines+n, [](Line a, Line b){ return a.id < b.id; });
    double ans = INF;
    do {
        vector existing = {四條邊界};
        double cur = 0;
        for (int i=0; i