在区间上贪心，存储的是包括该点的范围
#include<iostream>#include<algorithm>#include<cmath>using namespace std;struct point{double x1,x2;}p[1005];<span style="color:#008000;">//</span><span style="color:#008000;">每个岛作半径为d的圆，与x轴所截的线段</span>bool cmp(point a,point b){return a.x1<b.x1;}int main(){int n,r,i,t,end_flag,count;double temp,x,y;t=1;while(cin>>n>>r){if(n==0&&r==0) break;end_flag=0;count=1;for(i=1;i<=n;i++){cin>>x>>y;if(y>r) end_flag=1;p[i].x1=x-sqrt(r*r-y*y);p[i].x2=x+sqrt(r*r-y*y);}//存储的是包括该点的范围cout<<"Case "<<t++<<": ";if(end_flag){cout<<-1<<endl;continue;}sort(p+1,p+n+1,cmp);temp=p[1].x2;for(i=2;i<=n;i++){if(p[i].x2<temp) temp=p[i].x2;//如果下一个区间在当前区间的内部。else if(p[i].x1>temp)//如果下一个区间不在当前区间内。{count++;temp=p[i].x2;}//不考虑两个区间有交集，，此时雷达还是限制在原区间右端点。}cout<<count<<endl;}return 0;}
往往教导我们大家要好好学习天天向上，要永不言弃坚持到底百折不挠宁死不屈，
