Radar equipment (greedy)

  analysis ： First, give the location of an island , We can find out the position range where this radar can be placed , It means that as long as the radar is placed in this section , Then the island can be covered by radar , Altogether n An island , Then the corresponding can also be found n Intervals , At this time, there should be at least one radar in each section , But there may be coincidence between intervals Of , In other words, we require a minimum number of radars so that there is at least one radar in each interval , Then this is obviously a greedy problem , Let's sort all the intervals according to the right endpoint , Then we record a r Represents the location of the last radar , If the current range is r To the right of , Then we should at least install another radar , Because there is no longer an island on the left side of the current range that is not covered , So our radar is placed on the right as far as possible , But also within the current range , So it is placed on the right end of the current interval , Place in sequence , Add the number of radars every time you place one 1, Finally, output the number of radars .

Here is the code ：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=1003;
int n,d;
struct node{
	double l,r;
}p[N];
bool cmp(node a,node b)
{
	return a.r<b.r;
}
void f(int i,int x,int y)
{
	p[i]={x-sqrt(1.0*d*d-y*y),x+sqrt(1.0*d*d-y*y)};
}
int main()
{
	cin>>n>>d;
	int x,y;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&x,&y);
		if(y>d)
		{
			puts("-1");
			return 0;
		}
		f(i,x,y);
	}
	sort(p+1,p+n+1,cmp);
	double r=-9999;
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(p[i].l>r)
		{
			r=p[i].r;
			cnt++;
		} 
	}
	printf("%d",cnt);
	return 0;
}