BZOJ 2300 [HAOI2011] 防線修建：動態凸包離線維護

問題建模

平面上給定n+2個點：河邊兩端(0,0)、(n,0)、首都(x,y)（必須保護），其餘m個城市坐標(a,b)（00）。初始所有城市受保護，防線為凸包上鏈（河邊作為天然邊）。操作：
1) 取消第i個城市保護（刪除點）
2) 詢問當前防線總長度（凸包周長扣除河邊）
m≤10^5, q≤2×10^5，需離線處理。

核心洞見：刪除轉添加

凸包動態刪點極難，但動態加點可維護。離線策略：
1. 讀取所有操作，標記被刪除的點。
2. 初始凸包僅含未被刪除的點（含三個必保護點）。
3. 逆序處理操作：遇刪除→加點；遇詢問→記錄當前答案。
4. 正序輸出詢問答案。

動態凸包維護：有序集合 + 幾何判斷

凸包上鏈點按x單調遞增，用set<Point>維護（比較函數按x再y）。加點P：

1. 若P在現有凸包內（或邊上），忽略。
2. 在set中lower_bound找到右鄰點R，左鄰點L = prev(R)。
3. 若L、P、R構成凸角（向量叉積(R-L)×(P-L) < 0），則P在凸包外，需插入並清理兩側凹點。
   向右：而next(T)與T、P構成凹角（(next(T)-P)×(T-P) > 0），刪除T，更新周長。
   向左：同理清理。
   最後插入P，更新周長增量|L-P| + |P-R| - |L-R|。

關鍵幾何工具

struct Point { int x, y; };
Point operator-(Point a, Point b) { return {a.x-b.x, a.y-b.y}; }
long long cross(Point a, Point b) { return 1LL*a.x*b.y - 1LL*a.y*b.x; }
double dist(Point a, Point b) { return sqrt(1.0*(a.x-b.x)*(a.x-b.x) + 1.0*(a.y-b.y)*(a.y-b.y)); }
bool inHull(Point p) { // 判斷是否在當前凸包內
    auto r = hull.lower_bound(p);
    if (r == hull.end() || r == hull.begin()) return false;
    auto l = prev(r);
    return cross(*r - *l, p - *l) <= 0; // 在邊右側或上
}

複雜度與細節

• 每個點最多進出set一次，均攤O(log n)。
• 總複雜度O((m+q) log m)。
• 雙精度輸出保留兩位小數：printf("%.2f\n", ans)。
• 初始三點構成三角形，周長為兩條斜邊之和。

樣例演示

輸入：4 2 1 / 2 / 1 2 / 3 2 / 5 / 2 / 1 1 / 2 / 1 2 / 2
過程：初始凸包含(0,0)(4,0)(2,1)(1,2)(3,2) → 周長6.47
刪(1,2) → 周長5.84
刪(3,2) → 周長4.47