112. 雷达设备(贪心)

题目 几个月前做过的题，算法测验的时候忘了咋做了，时间太紧，胡诌了一个做法上去，不是正解。。。 基础掌握的不够扎实，重新复习。

  题意: 给定n个点(x,y),现在要在x轴放若干个雷达，每个雷达可以覆盖的范围为一个半径为d的圆。用尽可能少的点进行点覆盖。   思路: 首先进行问题转化，对于每个点(x,y)，它能被雷达覆盖的范围是固定的。属于区间[x - dis,x + dis]. dis = sqrt(d * d - y * y) 也就是说，只需要在[x - dis,x + dis]上任意位置放一个雷达即可完成对于该点的覆盖。 那么该题就转化成了一个经典的最小点覆盖问题，对区间右端点进行排序，扫描一遍，没有覆盖过的就新开一个区间。 时间复杂度: O(nlogn) 代码:

#include
using namespace std;
int n,m;
struct node{
    double a,b;
    bool operatorn>>m;
    bool flag = true;
    for(int i=0;i>x>>y;
        if(abs(y) > m)
        {
            flag = false;
        }
        a[i].a = x - sqrt(m * m - y * y);
        a[i].b = x + sqrt(m * m - y * y);
    }
    if(!flag)
    {
        puts("-1");
        return 0;
    }
    sort(a,a+n);
    int ans = 0;
    double ed = -2e9;
    for(int i=0;i ed)
        {
            ed = a[i].b;
            ans ++ ;
        }
    }
    cout