POJ 2932 Coneology：掃描線 + 有序集合求不被包含的圓

題目簡介

給定 n 個不相交的圓，求不被其他圓包含的圓的個數及其索引。n ≤ 40,000。

解題思路：掃描線 + 二叉搜索樹

將每個圓投影到 x 軸，得到左端點 (x-r) 和右端點 (x+r)。按 x 排序所有端點事件。掃描線從左向右移動，維護一個有序集合（按 y 座標）存儲當前活躍的圓。關鍵性質：若圓 A 包含圓 B，則在掃描線經過 B 的左端點時，A 必已在集合中且 y 座標最接近 B。因此只需檢查集合中 B 的前驅和後繼是否包含 B。若均不包含，則 B 為外部圓，加入答案並插入集合；遇到右端點則從集合刪除。

代碼實現

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
const int MAXN = 40012;
double x[MAXN], y[MAXN], r[MAXN];
vector<pair<double,int>> events;
set<pair<double,int>> active; // (y, id)
vector<int> ans;

bool inside(int i, int j) { // i 是否在 j 內
    double dx = x[i]-x[j], dy = y[i]-y[j], dr = r[i]-r[j];
    return r[i] <= r[j] && dx*dx + dy*dy <= dr*dr;
}

int main() {
    int n; scanf("%d", &n);
    for (int i=0;i= 0) { // 左端點
            auto it = active.lower_bound({y[id], id});
            if (it != active.end() && inside(id, it->second)) continue;
            if (it != active.begin() && inside(id, prev(it)->second)) continue;
            ans.push_back(id);
            active.insert({y[id], id});
        } else { // 右端點
            active.erase({y[~id], ~id});
        }
    }
    sort(ans.begin(), ans.end());
    printf("%d\n", (int)ans.size());
    for (int id : ans) printf("%d ", id+1);
    return 0;
}

複雜度分析

排序 O(n log n)，集合操作每個端點 O(log n)，總時間 O(n log n)，空間 O(n)。