【YbtOJ】雷达装置

题目

#include<bits/stdc++.h>
#define reint register int
#define ll long long
using namespace std;
struct nod{    //存雷达区间
    double l,r;
}f[1005];
int x[1005],y[1005],ans;
bool cmp(nod a,nod b){   //按右边缘排序
    return a.r<b.r;
}
int main(){
    int n,d;
    scanf("%d%d",&n,&d);
    for(reint i=1;i<=n;++i){
        scanf("%d%d",&x[i],&y[i]);
        if(abs(y[i])>d){   //如果无法与x边相交
            puts("-1");
            return 0;
        }
    }
    for(reint i=1;i<=n;++i){
        f[i].l=x[i]-sqrt(1ll*d*d-1ll*y[i]*y[i]);   //勾股计算左区间
        f[i].r=x[i]+sqrt(1ll*d*d-1ll*y[i]*y[i]);   //勾股计算右区间
    }
    sort(f+1,f+n+1,cmp);  //排序
    ans=1;  //计数
    double pos=f[1].r;  //现在第一个区间的右边缘建雷达
    for(reint i=2;i<=n;++i){
        if(f[i].l<=pos&&f[i].r>=pos)  //如果区间内已经有雷达
            continue;
        else
            ans++,pos=f[i].r;    //否则新增雷达
    }
    cout<<ans;
    return 0;
}