POJ 1328 Radar Installation：貪心區間覆蓋最少雷達數

題目大意

海岸線為 x 軸，n 個島嶼座標 (x_i, y_i)（y_i > 0）。雷達安裝在海岸線上，覆蓋半徑 d。求最少雷達數覆蓋所有島嶼，若有島嶼 y_i > d 則無解輸出 -1。

核心轉化：區間覆蓋問題

• 島嶼 (x,y) 可被覆蓋的雷達位置區間為 [x - √(d²-y²), x + √(d²-y²)]。
• 問題轉為：在數線上選最少點，使每個區間至少包含一點（經典「區間點覆蓋」貪心問題）。

貪心策略

1. 計算所有島嶼的覆蓋區間 [L_i, R_i]。
2. 按 L_i 升序排序（L_i 相同按 R_i 升序）。
3. 掃描：維護當前雷達位置 pos（初始為第一區間的 R_1）。
4. 對每區間 [L,R]：若 L > pos，需新增雷達，pos = R，計數+1；否則 pos = min(pos, R)（縮小共同覆蓋範圍）。

完整代碼 (C++)

#include <cstdio>
#include <cmath>
#include <algorithm>
struct Seg { double l, r; } seg[1005];

bool cmp(const Seg& a, const Seg& b) {
    return a.l < b.l || (a.l == b.l && a.r < b.r);
}

int main() {
    int n, d, cas = 0;
    while (scanf("%d%d", &n, &d) == 2 && (n||d)) {
        bool impossible = false;
        for (int i=0;i d) impossible = true;
            double delta = sqrt(d*d - y*y);
            seg[i].l = x - delta;
            seg[i].r = x + delta;
        }
        if (impossible) { printf("Case %d: -1\n", ++cas); continue; }
        std::sort(seg, seg+n, cmp);
        int ans = 1;
        double pos = seg[0].r;
        for (int i=1;i pos) { ++ans; pos = seg[i].r; }
            else pos = std::min(pos, seg[i].r);
        }
        printf("Case %d: %d\n", ++cas, ans);
    }
    return 0;
}

關鍵細節

• 排序鍵值：l 升序，r 升序（保證同起點區間優先處理較短者）。
• 掃描時 pos = min(pos, R) 是關鍵：維護所有已覆蓋區間的交集右端點，確保後續區間判斷正確。
• 精度：double 足夠，輸出整數無精度問題。

複雜度

• 時間 O(n log n)，空間 O(n)。

總結

Radar Installation 是「區間點覆蓋」貪心的教科書級應用。幾何轉區間、排序掃描、維護交集右端點，三步構建完整解法。掌握此模板可解決所有類似「最少資源覆蓋需求區間」問題。