HDU 1007 / POJ 1007 Wall：凸包周長與格雷厄姆掃描法

問題描述

給定 N 個點（城堡頂點），求包含所有點且距離每個點至少 L 的最短圍牆長度。等價於：求點集凸包周長，再加上半徑為 L 的圓周長（2πL）。結果四捨五入到英尺（精度 8 英寸 = 2/3 英尺）。

格雷厄姆掃描法求凸包

1. 找基點：最低點（y 最小，同 y 取 x 最小），作為極角排序原點 p0。
2. 極角排序：其餘點按與 p0 連線極角從小到大排序；共線時按距離 p0 從近到遠。
3. 掃描構建：維護棧，依次處理排序後的點。若新點使棧頂兩點轉向為「右轉或共線」（叉積 ≤ 0），彈出棧頂；最後壓入新點。最終棧內即為凸包頂點（逆時針序）。

關鍵幾何運算

• 向量叉積：(b-a) × (c-a) > 0 表示 a→b→c 左轉。
• 距離平方：避免開根號比較距離。
• 周長計算：凸包頂點首尾相連求和，再加 2 * PI * L。

代碼框架

struct Point { double x, y; };
double cross(Point a, Point b, Point c) { // (b-a) x (c-a)
    return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
}
double dist(Point a, Point b) { return hypot(a.x-b.x, a.y-b.y); }

int graham(Point p[], int n, Point ch[]) {
    if (n < 3) return -1;
    // 1. find p0
    for (int i=1;i EPS) return cr > 0;
        return dist2(p0, a) < dist2(p0, b);
    });
    // 3. scan
    int top = 2;
    ch[0] = p[0]; ch[1] = p[1];
    for (int i=2;i1 && cross(ch[top-2], ch[top-1], p[i]) <= EPS) --top;
        ch[top++] = p[i];
    }
    return top;
}

精度與輸出

結果用 printf("%.0f\n", ans) 四捨五入到整數英尺。多測試用例之間需輸出空行。

總結

Wall 題是凸包周長的直接應用。格雷厄姆掃描 O(N log N) 是標準解法，關鍵在於極角排序與叉積判斷轉向的正確處理。理解凸包的幾何意義與代碼模板，是計算幾何入門的必修課。