poj1328——Radar Installation

贪心算法。

策略：先用d和岛屿坐标求出每个岛屿对应的雷达在x轴上的区间。利用贪心，使得求出的雷达落在尽可能多的区间里。

#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<math.h>
using namespace std;
#define N  1005
double a[N][2];
int n;
double d;
class point
{
public:
	double lx,rx;
};
point p[N];
double cmp(point x,point y)
{
	if(x.lx <=y.lx ) return true;
	return false;
}
void solve()
{
	int i,j;
	for(i=0;i<n;i++)
	{
		p[i].lx =a[i][0]-sqrt(d*d-a[i][1]*a[i][1]);
		p[i].rx =a[i][0]+sqrt(d*d-a[i][1]*a[i][1]);
	}
	sort(p,p+n,cmp);
	int sum=1;
	double std=p[0].rx ;
	for(i=1;i<n;i++)
	{
		if(p[i].lx >std)
		{
			std=p[i].rx ;
			sum++;
		}
		else 
		{
			if(p[i].rx <std)
				std=p[i].rx ;
		}
	}
	cout<<sum<<endl;
}
int main()
{
	int i,ca=0;
	bool flag;
	while(cin>>n>>d)
	{
		if(n==0&&d==0) break;
		flag=true;
		for(i=0;i<n;i++)
		{
			cin>>a[i][0]>>a[i][1];
			if(a[i][1]>d||d<=0) flag=false;
		}
		printf("Case %d: ",++ca);
		if(flag==false)
			cout<<-1<<endl;
		else 
			solve();
	}
	return 0;
}