POJ&&NYOJ--1328题Radar Installation

这个题用到了贪心算法，不过比较有技巧。嘿嘿，用了2个小时做出这个题。很有成就感。

题目大意： 海上有很多的小岛，我们需要在陆地上修建雷达，使得雷达能够完全覆盖过这些小岛来。提供雷达的半径和小岛的坐标，你的任务就是用最少的雷达把这些小岛覆盖过来。

解题思路：我们需要把这些小岛的坐标进行排序，这样方便进行数据处理。所以对小岛的横坐标进行排序，然后按照顺序一次进行判断。因为能够把一个小岛覆盖过来的雷达坐标有很多，所以我们只需要把边界判断一下即可。一些小的细节大家看代码吧。

原题地址：

POJ:点击打开链接。

NYOJ:点击打开链接。

代码如下：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
using namespace std;
struct spot//定义一个结构体。
{
	int x,y;//储存小岛的坐标.
	double r,l;//能够覆盖该岛的雷达的坐标范围、
}s[1001];
bool comp(spot a,spot b)
{
	if(a.x<b.x)return true;
	else return false;/*不想说这个小地方浪费了我将近半小时的时间*/
}
int main()
{
	int i,j,k,n,m=1,d;
    while(1)
	{   memset(s,0,sizeof(s));//清零结构体。
		scanf("%d %d",&n,&d);
	    if(n==0&&d==0)break;
		int flat=0; 
		for(i=0;i<n;i++)
		{	scanf("%d%d",&s[i].x,&s[i].y);
		    if(s[i].y>d) flat=1;	//如果超过雷达的覆盖半径，直接输出-1；
			s[i].l=s[i].x-sqrt((double)(d*d-s[i].y*s[i].y));//事实证明，在这个地方把雷达的左右范围求出来比在外面快的多。在poj上是两倍。
			s[i].r=s[i].x+sqrt((double)d*d-s[i].y*s[i].y);
		}
		if(flat)printf("Case %d: -%d\n",m,flat);
		else 
		{   int count=1;
	        sort(s,s+n,comp);
			double  min=s[0].l,max=s[0].r;
			for(i=1;i<n;i++)
			{
				if(s[i].l<=max)
				{
					if(s[i].l>min)min=s[i].l;//缩小范围。
					if(s[i].r<max)max=s[i].r;
				}
				else 
				{count++;//此处说明之前的雷达不能够覆盖过来，故雷达数量加一。
				 min=s[i].l;max=s[i].r;//更新雷达的左右范围。
				}
			}
			printf("Case %d: %d\n",m,count);//一定要注意格式。
		}m++;
	}
	return 0;
}

现在开始反思这个题，暴露出来自己的小习惯很不好，总是想当然。所以在进行sort排序的时候才会把那句“else return false”给故意省略掉。还有那个开方的函数掌握的也不是很扎实，自己都没有想起来double到底应该怎么写。这些东西其实稍微注意一下就可以做好的，但是自己还是在这上面浪费很长时间。唉，现在要提高自己写代码的速度了。

路漫漫其修远兮，吾将上下而求索！

（CSDN咋没个签名档呢？？？害的我每次都要自己手打！！！！）