C语言 雷达设置问题（贪心算法）

题目：雷达设置

假设滑行是一条无限长的直线。陆地在海岸的一边，大海在另一边。每个小岛都是位于海边的一个点。而任何雷达装置，定位在海岸上，只能覆盖d距离，所以海上的岛屿可以被半径装置覆盖，如果它们之间的距离最多为d。
我们使用笛卡尔坐标系，定义滑行是x轴。海面在x轴上方，陆面在x轴下方。给定海洋中每个岛屿的位置，以及雷达安装的覆盖距离，您的任务是编写一个程序，找出覆盖所有岛屿的雷达安装的最小数量。注意，一个岛的位置由它的x-y坐标表示。

输入：

输入由几个测试用例组成。每个case的第一行包含两个整数n (1<=n<=1000)和d，其中n为海上岛屿数量，d为雷达安装覆盖距离。然后是n行，每一行包含两个整数，表示每个岛的位置的坐标。然后，后面有一行空白来分隔这两种情况。
输入以包含一对0的行结束

输出：

对于每个测试用例输出一行，由测试用例号和所需的最小雷达安装数组成。“-1”安装对于这种情况意味着没有解决方案。

样例输入：

3 2
1 2
-3 1
2 1

1 2
0 2

0 0

样例输出：

Case 1: 2
Case 2: 1

思考：

① 把得到的岛屿x坐标按从小到大排序。
② 每个岛屿都有一个最有利的圆心，如下图所示，这个圆心是雷达的暂定位置：

③ 这样可以直接判断下个岛屿是否在雷达覆盖距离内，如果在范围内就不增加雷达个数，如果不在范围内，就以下个岛屿的最有利的位置放置雷达。
④ 而且如果第二个岛屿的最有利雷达位置比上个岛屿的最有利位置坐标小，则将雷达的坐标改成第二个岛屿的最有利雷达位置，这样一个雷达就可以覆盖两个岛屿。如下图，将暂定雷达位置cur_a改成雷达位置a。

代码：

#include<stdio.h>
#include<math.h>
struct Point
{
	int x;
	int y;	
}p[1005],temp; //存放岛屿坐标。
int main()
{
	int n,d,n_case=0;
	double a,cur_a;
	while(scanf("%d%d",&n,&d)!=EOF,n) //循环输入。
	{
		int i,j,flag=1;
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&p[i].x,&p[i].y);
			p[i].y=abs(p[i].y); //y都取y的绝对值。
		}
		for(i=0;i<n-1;i++) //冒泡排序。
		{
			for(j=0;j<n-i-1;j++)
			{
				if(p[j].x>p[j+1].x)
				{
					temp=p[j];
					p[j]=p[j+1];
					p[j+1]=temp; 
				}
			}
		}
		if(p[0].y<=d) //如果岛屿的y坐标大于半径d，直接返回-1。
		{ 
			j=1;
			cur_a=p[0].x+sqrt((double)(d*d-p[0].y*p[0].y)); //将第一个岛屿的雷达设为暂定雷达位置。
			a=cur_a; //设置确定雷达位置。
			for(i=1;i<n;i++) //从第二个开始比较。
			{
				if(p[i].y>d) //如果岛屿的y坐标大于半径d，直接返回-1。
				{
					flag=0;
					break;
				}
				cur_a=p[i].x+sqrt((double)(d*d-p[i].y*p[i].y)); //将每一个的岛屿的雷达设为暂定雷达位置。
				if(cur_a<=a) //如果暂定雷达位置小于确定雷达位置，则将暂定雷达位置设置为确定雷达位置，也就是雷达坐标往左移动。
				{
					a=cur_a; 
				}
				else 
				{
					if((((p[i].x-a)*(p[i].x-a)+p[i].y*p[i].y)>(d*d))) //大于确定雷达位置，则判断该岛屿是否在该确定雷达位置的覆盖范围内。
					{
						j++; //如果不在范围，则增加一个雷达。
						a=cur_a;
					}
					else
					{
						continue;
					}
				}
			}
			printf("Case %d: ",++n_case);
			if(flag)
			{
				printf("%d\n",j);
			}
			else
			{
				printf("-1\n");
			}
		}
		else
		{
			printf("Case %d: -1\n",++n_case);
		} 
	}
	return 0;
}