UVALive 3835:Highway(贪心 Grade D)

VJ题目链接

题意：平面上有n个点，在x轴上放一些点，使得平面上所有点都能找到某个x轴上的点，使得他们的距离小于d。求最少放几个点。

思路：以点为中心作半径为d的圆，交x轴为一个线段。问题转换成用最少的店覆盖所有的线段。经典贪心。按右点从小到大排序，然后从左往右扫，每次选择区间右点就行了。

代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

#define N 100100

bool eqs(double a, double b) {
    return fabs(a-b) < 1e-5;
}

struct Seg{
    double l, r;
    void get(int d) {
        int x, y;
        scanf("%d%d", &x, &y);
        double dx = sqrt(d*d-y*y+0.0);
        l = x - dx;
        r = x + dx;
    }
    bool operator < (const Seg &b) const {
        if (!eqs(r,b.r)) return r < b.r;
        return l < b.l;
    }
}seg[N];

int main(){
    int l;
    while (scanf("%d", &l) != EOF) {
        int d;
        scanf("%d", &d);
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            seg[i].get(d);
        }
        sort(seg, seg+n);

        int cnt = 0;
        double now = -0x3f3f3f3f;
        for (int i = 0; i < n; i++) {
            if (now < seg[i].l) {
                now = seg[i].r;
                cnt++;
            }
        }
        printf("%d
", cnt);
    }
    return 0;
}