学步园

开始个人想法是用x坐标从小到大排序，从左边往右找最大的坐标，并记下这个点，再找下一个不在以这个为圆心的圆内的点，再重复开始的步骤，

如果找到的坐标比上一个小，则坐标数不加，并将坐标改为那个小的点， 果断wa。

这有思路点小错，下面是正确的：

把点按横坐标排序，然后把每个点的雷达尽量往右放，然后每放一个雷达都要保证雷达左面的岛都被雷达所覆盖。所以我们可以按一个点靠右放完雷达后，再根据后面的在雷达位置左面的点，把雷达向左移。一个雷达经过了移的过程，就一定是能覆盖左面的岛。所以排好序后，只需O(n)

看了网上的思路是将每个点可能所在圆心的范围求出，在排序（以左端点进行），最后统计有多少部公共的区间；因为公共的区间一个雷达就ok了。

因为求得是范围所以需要用double类型

这是网上的代码；

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
struct node
{
	double d1,d2;
}q[10011];
bool cmp(node a,node b)
{
	if(a.d1==b.d1)
		return a.d2<b.d2;
	else
		return a.d1<b.d1;
}
int main()
{
	int i,j,n,num,kk=0;
	double d,a,b,k;
	while(~scanf("%d %lf",&n,&d))
	{
		if(n==0&&d==0.0)
			break;
		kk++;
		int flag=1;
		num=1;
		if(d<0)
			flag=0;
		for(i=1;i<=n;i++)
		{
			scanf("%lf%lf",&a,&b);
			if(b<0)
				flag=0;
			if(b>d)
				flag=0;
			q[i].d1=a*1.0-sqrt(d*d-b*b);
			q[i].d2=a*1.0+sqrt(d*d-b*b);
		}
		printf("Case %d: ",kk);
		if(flag==0)
		{
			printf("-1\n");
			continue;
		}
		sort(q+1,q+n+1,cmp);
		k=q[1].d2;
		for(i=2;i<=n;i++)
		{
			if(q[i].d1>k)
			{num++;
			k=q[i].d2;}
			else if(q[i].d2<k)
			{k=q[i].d2;
			}
		}
		printf("%d\n",num);
	}
	return 0;
}