🔗 UVA-1193 Radar Installation

tags: `排序(Sorting)`

範例程式碼已於 UVA、瘋狂程設(CPE) 上皆測試通過。

題意

在二維平面上存在一些小島 $islands = [x_i, y_i]$ ，其中 $(x_i, y_i)$ 表示第 $i$ 個小島的座標。

現在要在 x軸上安裝雷達偵測器，使得所有小島都能被雷達偵測到，且使得所需的雷達偵測器數量最少，問最少需要安裝多少雷達偵測器。

思路：排序 + 區間覆蓋

對於每個小島，首先可以求出放置雷達後，可以涵蓋這個島嶼的雷達其所屬的區間，即 $[x - \sqrt{d^2 - y^2}, x + \sqrt{d^2 - y^2}]$ ，可以畫圖理解。

如此問題便可以轉換成：在數線上有若干個區間，使用最少的點，使得每個區間內都至少有一個點。

這是一個經典的區間覆蓋問題，可以對所有區間依照右端點進行排序，然後從左到右遍歷。

令 $last$ 表示該組中第一個區間右端點，初始值為 $-\infty$ 。
對於每個區間 $[l, r]$ ，如果 $l > last$ ，則表示這個區間和上一組中的第一個區間不重疊，因此需要一個新的點，將 $r$ 設為新的 $last$ 。
否則，這個區間與同組中的所有區間皆有重疊部分，因此不需要新的點。證明如下：
- 由於已經按照右端點排序，故 $r > last$ ，這個區間與該組中的區間重疊的部分為 $[l, last]$
- 而該組中的所有區間，都包含了 $[last, last]$ ，故可以放置一個點在 $last$ 來使組內所有區間都存在至少一個點。

複雜度分析

時間複雜度： $O(n \log n)$ ，其中 $n$ 為小島的數量，每個小島會產生一個區間，故排序所有時間的的時間複雜度為 $O(n \log n)$ 。
空間複雜度： $O(n)$ ，存儲所有區間。

tc = 1
while True:
    # input
    line = input()
    if tc > 1: # 跳過空行
        line = input() 
    n, d = map(int, line.split())
    if n == 0 and d == 0:
        break
    islands = []
    for _ in range(n):
        line = input()
        islands.append(list(map(int, line.split())))
    
    flag = False
    intervals = []
    for x, y in islands:
        if y > d: # 不可能放置
            flag = True
            break
        dx = (d*d - y*y)**0.5
        intervals.append((x - dx, x + dx)) # 可以涵蓋這個島嶼的雷達其所屬的區間

    intervals.sort(key = lambda x: x[1]) # 按照右端點排序
    ans = 0
    last = -float("inf") # 上一個組的第一個區間的右端點
    for x, y in intervals:
        if x > last: # 和上一組的所有區間不重疊
            last = y
            ans += 1
    print(f"Case {tc}: {ans if not flag else -1}")
    tc += 1

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
#define endl '\n'

bool cmp(const pair<double, double>& a, const pair<double, double>& b) {
    return a.second < b.second;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, d, tc = 1, x, y;
    double dx;
    while (cin >> n >> d && n && d) {
        vector<pair<double, double>> intervals;
        bool flag = false;
        for (int i = 0; i < n; ++i) {
            cin >> x >> y;
            if (y > d) flag = true; // 不可能放置
            dx = sqrt(d * d - y * y);
            intervals.push_back({x - dx, x + dx}); // 可以涵蓋這個島嶼的雷達其所屬的區間
        }
        sort(intervals.begin(), intervals.end(), cmp); // 按照右端點排序
        int ans = 0;
        double last = (double) -INF; // 上一個組的第一個區間的右端點
        for (auto &i : intervals) {
            if (i.first > last) { // 和上一組的所有區間不重疊
                last = i.second;
                ans++;
            }
        }
        cout << "Case " << tc++ << ": " << (flag ? -1 : ans) << endl;
    }
    return 0;
}