UVA 10535 Shooter：激光射擊牆壁的角度掃描與區間重疊

題目

二維平面上有 n 梵牆 (線段)，射手位於 (x,y) 點，發射一條射線，求最多能擊穿多少牆壁。n ≤ 500，100 測試用例，5 秒時限。

幾何轉化

每牆壁對應射手視角的一個角度區間 [θ1, θ2]。射線方向落在區間內即擊中該牆壁。問題轉化為：求平面上重疊區間數的最大值。

區間構建

• 計算兩端點相對射手的極角：atan2(y1-y, x1-x), atan2(y2-y, x2-x)，範圍 (-π, π]。
• 確保 θ1 ≤ θ2。
• 若 θ2 - θ1 ≥ π，說明射線從另一側也能擊中，拆分為 [-π, θ1] 和 [θ2, π] 兩個區間。

掃描線算法

將所有區間端點建立事件：(angle, +1) 入區間，(angle, -1) 出區間。按角度排序，同角度入事件優先 (+1 > -1)。掃描累加計數，最大值即答案。

代碼關鍵片段

struct Event { double ang; int delta; };
bool cmp(Event a, Event b) {
    if (fabs(a.ang - b.ang) > 1e-9) return a.ang < b.ang;
    return a.delta > b.delta; // 入優先
}
int solve() {
    vector ev;
    for (each wall) {
        double a1 = atan2(y1-y, x1-x), a2 = atan2(y2-y, x2-x);
        if (a1 > a2) swap(a1, a2);
        if (a2 - a1 >= PI) {
            ev.push_back({-PI, +1}); ev.push_back({a1, -1});
            ev.push_back({a2, +1}); ev.push_back({PI, -1});
        } else {
            ev.push_back({a1, +1}); ev.push_back({a2, -1});
        }
    }
    sort(ev.begin(), ev.end(), cmp);
    int cur = 0, ans = 0;
    for (auto& e : ev) { cur += e.delta; ans = max(ans, cur); }
    return ans;
}

精度處理

• 用 1e-9 比較浮點數相等。
• atan2 返回 (-π, π]，邊界 ±π 需統一處理。

複雜度

• 每用例：O(n log n) 排序，n ≤ 500 極快。
• 100 用例總時間遠小於 5 秒。