112. 雷达设备(贪心/逆向思考)

题目：

112. 雷达设备 - AcWing题库

?

输入样例：

3 2
1 2
-3 1
2 1

输出样例：

2

思路：?

?

代码：

?

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include<cmath>
using namespace std;
const int N=100010;
struct interval//将雷达扫岛逆向考虑-->可覆盖该岛的雷达位置区间（二维变一维）
{
    double l,r;
    bool operator<(const interval& rhs){return r<rhs.r;}
}interval[N];
int main()
{
    int n,Len;
    cin>>n>>Len;
    int x,y;
    double len=0;
    for(int i=0;i<n;i++){
        scanf("%d%d",&x,&y);
        if(abs(y)>Len){cout<<"-1";return 0;}//表示该岛无法被任何位置的雷达扫到
        len=sqrt(abs(Len*Len-y*y));
        interval[i].l=x-len;interval[i].r=x+len;
    }
    sort(interval,interval+n);//按照区间右值排序
    int cnt=1;
    double pr=interval[0].r;
    for(int i=1;i<n;i++){
        if(pr<interval[i].l){
            pr=interval[i].r;
            cnt++;
        }
    }
    cout<<cnt;
}