HDU 1348 Wall：凸包 Graham Scan 求圍牆長度

問題描述

給定平面上 N 個點，求能包圍所有點的最短圍牆長度。圍牆需與所有點保持至少距離 L（輸入給定半徑 r），即在凸包外側擴展一條寬度為 r 的圍牆。最終長度 = 凸包周長 + 2πr（外側圓弧拼成一個完整圓）。

Graham Scan 算法步驟

1. 找基準點：選取 y 最小（同 y 取 x 最小）的點作為 p[0]。
2. 極角排序：其餘點按相對 p[0] 的極角（atan2）升序排序；極角相同則按距離 p[0] 從遠到近（或近到遠，視實現而定，代碼中同角度取 x 大、y 大者優先）。
3. 掃描構建凸包：維護棧 ch[]，依序處理排序後的點。對於新點 p[i]，若棧頂兩點與 p[i] 構成非左轉（叉積 ≤ 0），彈出棧頂；重複直到左轉或棧剩 <2 點，再將 p[i] 入棧。
4. 計算周長：累加棧中相鄰點距離，加上首尾距離，最後加 2πr。

關鍵代碼片段

struct point { double x, y, angel; } p[1005], ch[1005];

double cross(point a, point b, point c) {
    double x1 = b.x - a.x, y1 = b.y - a.y;
    double x2 = c.x - b.x, y2 = c.y - b.y;
    return x1 * y2 - x2 * y1;
}

bool cmp_angle(point a, point b) {
    if (a.angel == b.angel) {
        if (a.x == b.x) return a.y > b.y;
        return a.x > b.x;
    }
    return a.angel < b.angel;
}

int main() {
    int t, n; double r;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%lf", &n, &r);
        for (int i = 0; i < n; ++i) scanf("%lf%lf", &p[i].x, &p[i].y);
        sort(p, p + n, [](point a, point b) {
            return a.y == b.y ? a.x < b.x : a.y < b.y;
        });
        for (int i = 1; i < n; ++i)
            p[i].angel = atan2(p[i].y - p[0].y, p[i].x - p[0].x);
        sort(p + 1, p + n, cmp_angle);

        ch[0] = p[0]; ch[1] = p[1]; ch[2] = p[2];
        int top = 3;
        for (int i = 3; i < n; ++i) {
            while (top > 2 && cross(ch[top-2], ch[top-1], p[i]) <= 0) --top;
            ch[top++] = p[i];
        }
        double len = dist(ch[0], ch[top-1]);
        for (int i = 1; i < top; ++i) len += dist(ch[i], ch[i-1]);
        len += 2 * PI * r;
        printf("%.0lf\n", len);
        if (t) puts("");
    }
    return 0;
}

注意事項

• 叉積判斷左轉：cross > 0 為左轉，≤ 0 彈出（包含共線點，視題意決定是否保留邊界點）。
• 極角相同點的排序：代碼中同角度取 x、y 較大者優先，配合掃描邏輯可正確處理共線情況。
• 最終周長加 2πr：幾何意義為凸包外側等距離 r 的曲線長度等於凸包周長 + 一個圓周長。
• 輸出格式：每組測試案例後輸出空行（除最後一組）。

複雜度

• 排序 O(N log N)，掃描 O(N)，總時間 O(N log N)，N ≤ 1000 完全足夠。

總結

HDU 1348 是凸包模板題的典型應用，結合幾何性質「外擴圍牆長度 = 凸包周長 + 2πr」，考察 Graham Scan 實現細節：基準點選取、極角排序、叉積判斷、共線點處理。代碼簡潔高效，是計算幾何入門必刷題目。