POJ 1113：Wall - 凸包周長 + 圓周率應用

問題描述

給定凸多邊形城堡頂點 (按順序給出)，城牆需距離城堡至少 L 英尺。求最短城牆長度（四捨五入到英尺）。

幾何結論

最短城牆 = 城堡凸包周長 + 半徑 L 的圓周長 (即 2πL)。因為城牆在每條邊外側平移 L，轉角處形成圓弧，總圓弧角度和為 360°。

算法步驟

1. 讀入點，找最低最左點作為極角排序基準。
2. 極角排序 (Graham Scan 核心)。
3. 掃描構建凸包：叉積判斷左轉/右轉/共線，共線保留最遠點。
4. 計算凸包周長。
5. 答案 = 周長 + 2 * π * L，四捨五入輸出整數。

代碼實現

#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-8;
const double PI = acos(-1.0);

struct Pt { double x, y; };
Pt operator-(Pt a, Pt b) { return {a.x-b.x, a.y-b.y}; }
double cross(Pt a, Pt b) { return a.x*b.y - a.y*b.x; }
double dist(Pt a, Pt b) { return hypot(a.x-b.x, a.y-b.y); }

bool cmp(Pt a, Pt b) { // 極角排序
    double cr = cross(a - base, b - base);
    if (fabs(cr) > EPS) return cr > 0;
    return dist(base, a) < dist(base, b);
}

int main() {
    int n; double L;
    while (cin >> n >> L) {
        vector p(n);
        for (auto &pt : p) cin >> pt.x >> pt.y;
        // 找基準點
        base = *min_element(p.begin(), p.end(), [](Pt a, Pt b){
            if (fabs(a.y - b.y) > EPS) return a.y < b.y;
            return a.x < b.x;
        });
        sort(p.begin(), p.end(), cmp);
        // Graham Scan
        vector ch;
        for (auto &pt : p) {
            while (ch.size() >= 2) {
                Pt v1 = ch.back() - ch[ch.size()-2];
                Pt v2 = pt - ch.back();
                if (cross(v1, v2) > -EPS) ch.pop_back(); // 非左轉
                else break;
            }
            ch.push_back(pt);
        }
        // 計算周長
        double perim = 0;
        for (int i = 0; i < ch.size(); ++i)
            perim += dist(ch[i], ch[(i+1)%ch.size()]);
        long long ans = llround(perim + 2 * PI * L);
        cout << ans << '\n';
    }
    return 0;
}

關鍵點

• 極角排序時共線點按距離排序，掃描時保留最遠。
• 叉積 > 0 為左轉，< 0 右轉，= 0 共線。
• llround 四捨五入到長整數。

總結

經典「凸包 + 緩衝區」問題：外擴距離 L 的周長 = 原周長 + 2πL。Graham Scan 求凸包是平面幾何基礎算法。