雷达设备

题目 雷达设备

image-fd319596

思路分析

image-badfdaa0

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N=1010;

struct Range{

    double l,r;

    bool operator<(const Range& other)const{

        return r<other.r;

    }

}ranges[N];

int n,d;

int main()

{

    cin>>n>>d;

    bool fail=false;

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

        int x,y;cin>>x>>y;

        if(y>d){

            fail=true;

            break;

        }

        double len=sqrt(d*d-y*y);

        ranges[i].l=x-len;

        ranges[i].r=x+len;

    }

    if(fail){

        cout<<-1;

        return 0;

    }

    int res=0;

    sort(ranges,ranges+n);

    double ed=-2e9;

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

        if(ranges[i].l>ed){

            res++;

            ed=ranges[i].r;

        }

    }

    cout<<res;

    return 0;

}

同类题型

视频讲解

⬅️ 最大不相交区间数量 🏠 00-刷题理模型 ➡️ k叉树 荷马史诗