BZOJ 1670 [USACO 2006 Oct] Building the Moat - 凸包周長最小化問題

問題描述

農夫約翰為了防止食蟻獸入侵農場，決定在農場周圍挖掘一條護城河。農場中有 N (8 ≤ N ≤ 5,000) 股泉水，護城河必須筆直連接相鄰的兩股泉水，形成一個封閉環路，並包圍所有泉水（泉水可在護城河內部或恰好在河道上）。目標是使護城河總長度最小。所有泉水座標均為 (1..10,000,000) 範圍內的整數點，且任意三股泉水不共線。

核心洞察

這是一個經典的凸包問題。能夠包圍所有點且周長最小的封閉多邊線，正是這些點集的凸包。凸包由最外層的點構成，連接它們即可得到最短圍繞路徑。

算法選擇：Graham Scan 掃描法

Graham Scan 時間複雜度 O(N log N)，適合 N ≤ 5,000 的規模。步驟如下：

1. 找到最低點（y 最小，若相同則 x 最小）作為基準點 p₀。
2. 其餘點按與 p₀ 的極角排序（極角相同則按距離升序）。
3. 維護一個棧，依序處理排序後的點：若新點導致棧頂兩點與新點形成非左轉（叉積 ≤ 0），則彈出棧頂點；重複直到滿足左轉條件，再將新點入棧。
4. 最終棧中點序即為凸包頂點（逆時針序）。

關鍵實現細節

struct Point { long long x, y; };
Point operator-(const Point& a, const Point& b) { return {a.x - b.x, a.y - b.y}; }
long long cross(const Point& a, const Point& b) { return a.x * b.y - a.y * b.x; }
long long dist2(const Point& a, const Point& b) { 
    long long dx = a.x - b.x, dy = a.y - b.y; 
    return dx*dx + dy*dy; 
}

排序比較函數利用叉積判斷極角大小，距離作為 tie-breaker。構建凸包時，條件 cross(stk[top]-stk[top-1], p[i]-stk[top-1]) <= 0 表示非左轉（共線或右轉），需彈出。最後在棧尾補上第一個點以閉合，累加邊長平方根得到周長。

範例驗證

樣本輸入 20 個點，輸出 70.87。對應圖示中凸包頂點序列為 (18,0)→(6,-6)→(0,-5)→(-3,-3)→(-17,0)→(-7,7)→(0,4)→(3,3)→回到起點，總長約 70.8700576850888，保留兩位小數即 70.87。

複雜度分析

• 排序：O(N log N)
• 掃描構建凸包：O(N)
• 空間：O(N)

完全符合題目限制（3 秒、64 MB）。

總結

本題是凸包模板題的典型應用。掌握 Graham Scan 或 Andrew 单调链算法，並注意叉積用 long long 防溢出、共線點處理、雙精度輸出格式控制，即可穩健解決。