题目链接

Radar Installation POJ - 1328

思路

考虑每个岛屿到海岸可行的区间，题意则转化成选出尽量少的点使得每个区间都包含其中一个点。

可以贪心求解，以右端点排序，查看左端点是否可以被包含。

时间复杂度

$$ O(Nlog(N)) $$

代码

#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

const int MAXN = 1e3 + 10;

int a[MAXN], b[MAXN];

pair<double, double> p[MAXN];

int main() {
    int n, r;
    int kase = 0;
    while (scanf("%d%d", &n, &r), n + r) {
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &a[i], &b[i]);// don't forget &
        }
        bool f = true;
        for (int i = 1; i <= n; i++) {
            if (b[i] > r) {
                f = false;
                break;
            } else {
                double w = sqrt(r * r - b[i] * b[i]);
                p[i].first = a[i] + w;
                p[i].second = a[i] - w;
            }
        }
        if (!f) {
            printf("Case %d: %d\n", ++kase, -1);
            continue;
        }
        sort(p + 1, p + 1 + n);
        double l = p[1].second;
        for (int i = 1; i <= n; i++) {
            l = min(l, p[i].second);
        }
        int ans = 0;
        l -= 10;
        for (int i = 1; i <= n; i++) {
            if (p[i].second > l) {
                ans++;
                l = p[i].first;
            }
        }
        printf("Case %d: %d\n", ++kase, ans);
    }

    return 0;
}