这题的话首先判断下岛的纵坐标是否大于雷达的覆盖范围，是的话就一定不能覆盖，否的话以岛的坐标为圆心画圆，用一个结构体数组记录下与x轴的的左右交点，
接下来可以对右交点从小到大排序，以第一个坐标的右交点为比较变量，然后遍历一遍就可以了，如果当前的左交点大于该右交点，雷达的数目加一，右交点更新为当前交点的右交点。也可以对左交点从小到大排序，不过这样的话，比较的时候就得多考虑一种情况，也就是当前区间被前一区间完全覆盖，这时右交点就要更新为当前区间的右交点。
这是对右交点排序的代码
#include<stdio.h> #include<math.h> struct node { double r; double l; }pos[10000]; int main() { int n,d,i,j,flag,ans,cnt=1; int x,y; double t; while(scanf("%d %d",&n,&d)!=EOF) { flag=0; ans=1; if(n==0&&d==0) break; for(i=0;i<n;i++) { scanf("%d %d",&x,&y); if(y>d)//一定不能覆盖 flag=1; pos[i].l=(x)-sqrt((double)(d*d-y*y));//以岛为圆心画圆与x轴的左右交点 pos[i].r=(x)+sqrt((double)(d*d-y*y)); } if(flag) { printf("Case %d: %d ",cnt++,-1); continue; } for(i=0;i<n-1;i++)//按右交点从小到大排序 for(j=i+1;j<n;j++) { if(pos[i].r>pos[j].r) { t=pos[i].r; pos[i].r=pos[j].r; pos[j].r=t; t=pos[i].l; pos[i].l=pos[j].l; pos[j].l=t; } } double temp; temp=pos[0].r; for(i=1;i<n;i++) { if(pos[i].l>temp)//当前左交点大于右交点更新右交点，雷达数加一 { temp=pos[i].r; ans++; } } printf("Case %d: %d ",cnt++,ans); } return 0; }
这是对左交点排序的代码
#include<stdio.h> #include<math.h> struct node { double l; double r; }pos[10000]; int main() { int n,d,cnt=1,ans,i,j,x,y,flag; while(scanf("%d %d",&n,&d)!=EOF) { flag=0; ans=1; if(n==0&&d==0) break; double t,temp; for(i=0;i<n;i++) { scanf("%d %d",&x,&y); if(y>d) flag=1; pos[i].l=x-sqrt((double)(d*d-y*y)); pos[i].r=x+sqrt((double)(d*d-y*y)); } if(flag) { printf("Case %d: %d ",cnt++,-1); continue; } for(i=0;i<n-1;i++) for(j=i+1;j<n;j++) { if(pos[i].l>pos[j].l) { t=pos[i].l; pos[i].l=pos[j].l; pos[j].l=t; t=pos[i].r; pos[i].r=pos[j].r; pos[j].r=t; } } temp=pos[0].r; for(i=1;i<n;i++) { if(pos[i].l>temp) { temp=pos[i].r; ans++; } else if(pos[i].r<temp) temp=pos[i].r; } printf("Case %d: %d ",cnt++,ans); } return 0; }