雷达设备

AcWing-112-雷达设备

分析

见《进阶指南》第43页。

最少覆盖区间点数=最多不相交区间数。

实现

#include <iostream>
#include <cmath>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;

const int N = 1010;
struct node {
    double l, r;
    bool operator < (const node& o) const {
        return r < o.r;
    }
};
node a[N];

int main () {
    int n;
    double d;
    scanf("%d%lf", &n, &d);

    for (int i = 1; i <= n; ++ i) {
        double x, y;
        scanf("%lf%lf", &x, &y);
        if (y > d) {
            printf("-1");
            return 0;
        }
        a[i].l = x - sqrt(d * d - y * y);
        a[i].r = x + sqrt(d * d - y * y);
    }

    sort(a + 1, a + n + 1);
    int res = 0;
    double prev = -inf;
    for (int i = 1; i <= n; ++ i) {
        if (prev < a[i].l) {
            prev = a[i].r;
            ++ res;
        }
    }
    printf("%d", res);
    return 0;
}