BZOJ 1043 HAOI 2008 下落的圓盤：計算幾何與區間合併

BZOJ 1043 HAOI 2008 下落的圓盤：計算幾何與區間合併

題目給出一系列按時間順序落下的圓盤，後落下的圓盤會覆蓋先前的。求最終可見的圓周總長度。這是一道結合計算幾何與掃描線思想的經典問題。

核心思路：從後向前處理，求可見弧長

對於每個圓盤，只需考慮它之後落下的圓盤對其的遮擋。將遮擋部分在圓周上投影為角度區間，合併所有遮擋區間，剩餘未被覆蓋的弧長即為該圓盤可見部分。累加所有圓盤的可見弧長即為答案。

兩圓相交區間的幾何計算

設兩圓半徑為 R、r，圓心距 d。若 d ≥ R + r 無交集；若 d ≤ |R - r| 一圓內含另一圓。否則利用餘弦定理求出夾角 θ = acos((R² + d² - r²) / (2Rd))，結合向量極角 α，可得相交弧對應的角度區間 [α - θ, α + θ]。需處理跨越 0/2π 邊界的情況，拆分為兩個區間。

區間合併與最終計算

將所有遮擋區間按起始角度排序，掃描合併重疊區間，得到總遮擋角度。可見角度 = 2π - 遮擋角度，可見弧長 = 可見角度 × 半徑。時間複雜度 O(n² log n)，n ≤ 1000 可接受。

關鍵代碼片段

inline void InsertInterval(const Circle &a, const Circle &b) {
    double dis = Calc(a.o, b.o);
    if (dis > a.r + b.r) return;
    if (dis < a.r - b.r) return;
    if (dis < b.r - a.r) { interval[++cnt] = Interval(0, 2 * PI); return; }
    
    Point u = b.o - a.o;
    double alpha = atan2(u.y, u.x) + PI;
    double delta = acos((a.r * a.r + dis * dis - b.r * b.r) / (2 * a.r * dis));
    
    if (alpha - delta < 0) {
        interval[++cnt] = Interval(alpha - delta + 2 * PI, 2 * PI);
        interval[++cnt] = Interval(0, alpha + delta);
    } else if (alpha + delta > 2 * PI) {
        interval[++cnt] = Interval(alpha - delta, 2 * PI);
        interval[++cnt] = Interval(0, alpha + delta - 2 * PI);
    } else {
        interval[++cnt] = Interval(alpha - delta, alpha + delta);
    }
}

本題展示了計算幾何中「角度掃描 + 區間合併」的通用技巧，對處理圓形遮擋、可見區域等問題極具參考價值。