题目链接：https://www.acwing.com/problem/content/114/
解决思路：我们所要找到的是雷达的最小数目，因此我们需要对每个小岛进行大都分析
①求出能够到达他的海岸线的范围，通过d与y我们可以求出他的x轴上的覆盖范围，（l,r），然后按照区间的右端点排序。
②求出每个岛的覆盖范围后，我们需要找出最少的使用雷达的数量，如果当前区间包括下一点的区间范围，则直接跳过；如果当前区间不能包含下一个区间，则增加一个雷达数目，并且将雷达范围更新为下一个雷达的区间。
例如下图所示：只需要三个雷达即可
代码：
#include<iostream> #include<cmath> #include<cstdio> #include<algorithm> using namespace std; const int N=10101; struct node { double l,r; bool operator <(const node &t)const { return r<t.r; } }s[N]; int main() { int i,j,n,d,x,y; bool flag=false; scanf("%d%d",&n,&d); for(i=0;i<n;i++) { scanf("%d%d",&x,&y); if(y>d) flag=true; else { double len=sqrt(d*d-y*y); s[i].l=x-len;s[i].r=x+len;//计算每个岛的区间 } } if(flag==true) { puts("-1"); } else { sort(s,s+n);//按照区间右端点排序 int cnt=0; double nowl=-1e20; for(i=0;i<n;i++) { if(nowl<s[i].l)//判断当前取件是否有下一个区间的点 { cnt++; nowl=s[i].r;//更新区间 } } printf("%d\n",cnt); } return 0; }