转载请注明出处：http://blog.csdn.net/u012860063?viewmode=contents

题目链接：http://poj.org/problem?id=1328

Description

Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the coasting, can only cover d distance, so an island in the sea can be covered by a radius installation, if the distance between them is at most d. 

We use Cartesian coordinate system, defining the coasting is the x-axis. The sea side is above x-axis, and the land side below. Given the position of each island in the sea, and given the distance of the coverage of the radar installation, your task is to write a program to find the minimal number of radar installations to cover all the islands. Note that the position of an island is represented by its x-y coordinates.
 
Figure A Sample Input of Radar Installations

Input

Output

Sample Input

3 2
1 2
-3 1
2 1

1 2
0 2

0 0

Sample Output

Case 1: 2
Case 2: 1

思路：反向思考把每个岛屿能到达的左区间和右区间用结构体记录，再用贪心的思想计算雷达数；

代码如下：

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
struct point
{
	double r,l;
}P[1017];
bool cmp(point a,point b)
{
	return a.l < b.l;
}
int main()
{
	int n, m, r, flag;
	int i, j;
	int x, y;
	int cas = 0, cont;
	while(cin>>n>>r)
	{
		if(n == 0 && r == 0)
			break;
		flag = cont = 0;
		for(i = 0; i < n; i++)
		{
			cin>>x>>y;
			if(fabs(y) > r)
			{
				flag = 1;
			}
			P[i].l = x*1.000-sqrt(r*r*1.00-y*y*1.000);
			P[i].r = x*1.000+sqrt(r*r*1.00-y*y*1.000);
		}
		cout<<"Case "<<++cas<<": ";
		if(flag)
		{
			cout<<"-1"<<endl;
			continue;
		}
		sort(P,P+n,cmp);
		cont = 1;
		double t = P[0].r;
		for(i = 1; i < n; i++)
		{
			if(P[i].r < t)//为了防止上一个岛屿的右区间比下一个岛屿的右区间还大的情况
			{//如果岛屿的右区间在雷达的左边，就需要移动雷达的位置到此岛屿的右区间
				t = P[i].r;
			}
			if(P[i].l > t)//如果下一个海岛的左区间在雷达的右边
			{//就需要再安一个雷达在此岛屿的有区间
				t = P[i].r;
				cont++;
			}
		}
		cout<<cont<<endl;
	}
	return 0;
}