POJ 1113 Wall：凸包與圓周長的巧妙結合

題目大意

國王要求建築師在城堡周圍建造一道牆，牆與城堡的最小距離至少為 L 英尺，且牆的長度必須最小。城堡形狀為多邊形，給定 N 個頂點座標（按順時針序），求滿足條件的最短牆長，結果四捨五入到英吋精度（誤差不超過 8 英吋）。

核心洞察

這是一個經典的計算幾何問題。關鍵在於發現：

• 最短牆的形狀 = 城堡凸包向外擴展距離 L 後的邊界
• 擴展後的邊界由兩部分組成：
  1. 與凸包邊平行且距離為 L 的直線段，總長度等於凸包周長
  2. 凸包各頂點處的圓弧，半徑為 L，所有圓弧拼湊成一個完整圓，總弧長 = 2πL

解題步驟

1. 求凸包：使用 Graham 掃描法（或 Andrew 算法）求出城堡頂點的凸包
2. 計算凸包周長：累加凸包相鄰頂點間的歐氏距離
3. 加上圓周長：答案 = 凸包周長 + 2 × π × L
4. 四捨五入輸出：題目要求精確到 8 英吋（1 英尺 = 12 英吋），即誤差 < 1/1.5 英尺，直接對結果加 0.5 取整即可

複雜度分析

• 排序：O(N log N)
• Graham 掃描：O(N)
• 總體：O(N log N)，N ≤ 1000 完全足夠

關鍵代碼片段

// Graham 掃描核心邏輯
sort(points+1, points+n+1, cmp); // 按極角排序
graham(); // 構建凸包

double ans = 0;
for (int i = 2; i <= top; ++i)
    ans += dist(stack[i-1], stack[i]); // 凸包周長
ans += 2 * PI * L; // 加上圓周長
printf("%d\n", int(ans + 0.5)); // 四捨五入

常見坑點

• 輸入頂點已按順時針序給出，但 Graham 掃描需要按極角排序，需先找最左下點作為基準
• 共線點的處理：題目保證無三點共線，但實現時需注意比較函數的嚴格性
• 精度問題：使用 double 計算，最終加 0.5 取整符合題目「精確到 8 英吋」要求

舉一反三

這類「多邊形向外擴展固定距離求周長/面積」的問題，核心公式皆為：
擴展後周長 = 原周長 + 2πL
擴展後面積 = 原面積 + 原周長×L + πL²
這是 Minkowski 和與幾何測度論的基礎應用。