http://www.cppblog.com/ArcTan/articles/167131.html
贪心。从左到右建立雷达,要尽量多地覆盖岛屿。以岛屿的圆心d为半径的圆与x轴有或者没有交点。如果存在没有交点的则不能实现!都存在交点的话,对于第i个岛屿计算出左右交点的x坐标保存在a[i],b[i]里。对a,b排序,然后一次从左到右找雷达。初始right=b[1]为当前最右边的左标,则对于下一个考虑岛屿i,如果a[i]>right则当前需要建立的雷达不能覆盖它,需要以此开始建立下一个雷达;否则,如果b[i]<right,则需要更新right=b[i],考虑下一个岛屿。
right记录的是当前雷达所能覆盖的最右的边界,只有当下一点的a[i]<=right,就不用再新建一个雷达, 但是,如果b[i]<right, 则为了覆盖到当前的点i,必须缩小雷达的右边界
如果a[i] >right, 需要新建一个雷达,并修改雷达的右边界right = b[i]
#include<stdio.h> double a[1003],b[1003]; int qsort(int s,int t) { int i,j; double mid,tmp; i=s;j=t;mid=a[(i+j)/2]; while (i<=j) { while (a[i]<mid) i++; while (a[j]>mid) j--; if (i<=j) { tmp=a[i];a[i]=a[j];a[j]=tmp; tmp=b[i];b[i]=b[j];b[j]=tmp; i++; j--; } } if (s<j) qsort(s,j); if (i<t) qsort(i,t); } int main() { int n,i,x,y,d,ans,flag,t; double right,xx; scanf("%d%d",&n,&d); t=0; while (n!=0||d!=0) { flag=0;t++; for (i=1;i<=n;i++) { scanf("%d%d",&x,&y); if (y>d) flag=1; xx=sqrt(d*d-y*y); a[i]=x-xx;b[i]=x+xx; } if (flag) { printf("Case %d: -1\n",t); scanf("%d%d",&n,&d); continue; } qsort(1,n); ans=0; right=b[1];i=2; while (i<=n) { if (a[i]>right) { ans++;right=b[i]; } if (b[i]<right) right=b[i]; i++; } ans++; printf("Case %d: %d\n",t,ans); scanf("%d%d",&n,&d); } }