acwing112. 雷达设备

题目

题解

大佬题解传送门：https://www.acwing.com/solution/content/1061/

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

const int N=1010;
typedef pair<double,double>pdd;
const double INF=1e10,eps=1e-6;
int n,d;
pdd seg[N];
int main(){
    cin>>n>>d;
    bool success=true;
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        if(y>d){
            success=false;
            break;
        }
        auto len=sqrt(d*d-y*y);
        seg[i]={x+len,x-len};
    }
    if(!success)puts("-1");
    else{
        sort(seg,seg+n);
        int res=0;
        double last=-INF;
        for(int i=0;i<n;i++){
            if(seg[i].second>last+eps){
                res++;
                last=seg[i].first;
            }
        }
        cout<<res<<endl;
    }
    
    return 0;
}