本文共 714 字，大约阅读时间需要 2 分钟。

雷达装置

题目链接：

题目描述

解题思路

首先，对于每个点来说，在哪个区间里放置雷达可以检测到它是可以求出来的，用勾股定理即可。

然后考虑贪心：如果想要放雷达数量尽量少，那么肯定要在区间的交界处放，因为每个都要放到，所以我们尽量往右放。

我们先以右端点为关键字进行排序，因为这个贪心是建立在右端点单调的基础上的。然后如果当前右端点容不下后面的左端点了，就新开存档，$ans++$ 即可。

code

#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>using namespace std;int n,d,ans;double h[1010];struct abc{   	double x,y;}a[1010];bool cmp(abc a,abc b){   	return a.y<b.y;}int main(){   	cin>>n>>d;	for(int i=1;i<=n;i++)	{   		int x,y;		scanf("%d%d",&x,&y);		if(y>d)		{   			cout<<-1<<endl;			return 0;		}		double t=sqrt(d*d-y*y);		a[i].x=x-t;		a[i].y=x+t;	}	sort(a+1,a+n+1,cmp);	h[++ans]=a[1].y;	for(int i=2;i<=n;i++)	{   		if(h[ans]<a[i].x)			h[++ans]=a[i].y;	}	cout<<ans<<endl;}