Radar equipment (greedy)

https://www.acwing.com/problem/content/description/114/

Suppose the coast is an infinite straight line , Land is on the side of the coast , The ocean is on the other side .

Each island is at a point on the side of the ocean .

Radar device All on the coastline , And the radar monitoring range is  d, When the distance between the island and a radar does not exceed  d  when , The island can be covered by radar .

We use Cartesian coordinates , Define the coastline as  x  Axis , One side of the sea is  x  Above the axis , The land side is  x  Below axis .

Now give the specific coordinates of each island and the detection range of radar , Please find out what can make All the islands are covered by radar Minimum number of radars required .

Input format

Enter two integers on the first line  n  and  d, They represent the number of islands and the range of radar detection .

Next  n  That's ok , Enter two integers per line , They represent the island  x,y Axis coordinates .

Separate the data in the same row with spaces .

Output format

Output an integer , Represents the minimum number of radars required , if If there is no solution, the required number of outputs  −1.

Data range

1≤n≤1000
−1000≤x,y≤1000

sample input ：

3 2
1 2
-3 1
2 1

sample output ：

2

Ideas ： Minimum radar coverage is required for all points , The area scanned by the radar is d The area of a circle with a radius , We try to transform this binary space into a one-dimensional space , That is, the range that the point can be covered by radar

  If you add another point (x1,y1)

  The radar range of these two points intersects , Description in Choose any point at the intersection of two intervals as the radar , Can cover these two points , According to this information , Let's record the interval , And sort according to the right endpoint , If the right end of the first interval is within the range of the following interval , It shows that there is an intersection , If it is less than the left end point of the following interval , It means there is no intersection .

  For the upper interval , Need at least 3 Only one radar can cover all points . So this question turns into Find interval , Sort , Greedy solution

Code segment ：

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef struct node{
        double a,b;
}p;
int cmp(node p1, node p2)// Sort in ascending order at the right endpoint 
{
    return p1.b < p2.b;

}
int main()
{
    int n,d;
    cin>>n>>d;
    int x,y;
    p k[1010];
    int ans=0;
    for(int i=0;i<n;i++)
    {
        cin>>x>>y;
        if(d*d<y*y)// If y Greater than d, Radar scan failed , Output -1
        {
            ans=1;
        }
        else{
        k[i].a=x-sqrt(d*d-y*y);// Find the left end point of the interval 
        k[i].b=x+sqrt(d*d-y*y);// Find the right endpoint of the interval 
        }
    }
    if(ans==1){cout<<"-1";}
    else {
    sort(k,k+n,cmp);
    double t=k[0].b;// Assign the right end of the first interval to t
    int count=1;
    for(int i=1;i<n;i++)
    {
        if(t<k[i].a)// If t This point is smaller than the left end of the next interval , It means there is no intersection 
        {
            count++;
            t=k[i].b;// Assign the right end of this interval to t, Overwrite the last right endpoint 
        }
    }
    cout<<count<<endl;
    }
    return 0;
}