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-;

}

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 = ; i < n; i++) {

            seg[i].get(d);

        }

        sort(seg, seg+n);

        int cnt = ;

        double now = -0x3f3f3f3f;

        for (int i = ; i < n; i++) {

            if (now < seg[i].l) {

                now = seg[i].r;

                cnt++;

            }

        }

        printf("%d\n", cnt);

    }

    return ;

}

巴特西

UVALive 3835:Highway(贪心 Grade D)

最新文章

热门文章