POJ 1106 Transmitters：半圓覆蓋最大點數幾何問題

題目大意

發射器位於 (x₀,y₀)，半徑 r，可旋轉半圓覆蓋區域。給定 N (≤150) 個點，求半圓旋轉後最多能覆蓋多少點。邊界上的點算覆蓋。

幾何轉化

• 點在半圓內 ⇔ 點到發射器距離 ≤ r **且** 點相對發射器的極角在某個長度為 π 的區間內
• 將所有在圓內的點轉為極角 θᵢ ∈ [0, 2π)
• 問題轉化為：在圓上找一個長度為 π 的弧，覆蓋最多極角點

掃描線算法

1. 計算所有有效點的極角，存入數組 `ang[]`
2. 排序 `ang`
3. 複製一份 `ang[i] + 2π` 追加到數組末尾，處理循環區間
4. 雙指針/二分：對每個 `ang[i]` 作為窗口左端，找最大 `j` 使 `ang[j] - ang[i] ≤ π`
5. 最大覆蓋數 = max(j - i + 1)

代碼實現

struct Point { double x, y; };
Point trans;
double r;
vector angles;

double dist(Point a, Point b) {
    return hypot(a.x-b.x, a.y-b.y);
}

int main() {
    while (cin >> trans.x >> trans.y >> r, r >= 0) {
        int n; cin >> n;
        angles.clear();
        for (int i = 0; i < n; ++i) {
            Point p; cin >> p.x >> p.y;
            if (dist(p, trans) <= r + 1e-9) { // 浮點誤差
                double ang = atan2(p.y - trans.y, p.x - trans.x);
                if (ang < 0) ang += 2*M_PI;
                angles.push_back(ang);
            }
        }
        sort(angles.begin(), angles.end());
        int m = angles.size();
        for (int i = 0; i < m; ++i) angles.push_back(angles[i] + 2*M_PI);
        
        int ans = 0;
        for (int i = 0, j = 0; i < m; ++i) {
            while (j < i+m && angles[j] - angles[i] <= M_PI + 1e-9) ++j;
            ans = max(ans, j - i);
        }
        cout << ans << '\n';
    }
}

關鍵細節

複雜度

• 時間：O(N log N) 排序主導，N ≤ 150 極快
• 空間：O(N)

延伸思考

若發射器也可移動，問題變為「最小覆蓋圓」或「最大空圓」，屬於更複雜的計算幾何問題。