poj1328 Radar Installation 【贪心】

题意：

有n个小岛，在x轴上方， 有一种雷达，覆盖范围为d，现在你可以在x轴以及x轴下方建立雷达，请问最少建立多个雷达可以覆盖所有的小岛

题解：

这是一道很经典的贪心入门题目， 从看到题意我们就知道 雷达建在x轴上是最优的，那么应该如何对这些小岛进行处理呢， 我们可以将每一个小岛的坐标信息来推出要覆盖到这个小岛的雷达， 要建在x轴上的哪些位置上，也就是一段区间，所以我们可以运用勾股定理，求出区间， 再对其进行排序，然后遍历一遍，贪心取最少的个数。做法如下：

AC_code:

/*
Algorithm: 贪心 
Author: anthony1314
Creat Time:
Time Complexity:
*/

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cstring>
#include<cstdio>
#include<cmath> 
//#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define mod 1e9 + 7
#define line printf("--------------");
using namespace std;
struct ff {
	double x, y;
} nn[1005];
struct node {
	double fir, end;
} kk[1005];
bool cmp(node aa, node bb) {
	if(aa.end == bb.end) {
		return aa.fir > bb.fir;
	}
	return aa.end < bb.end;
}
int n, d;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int caaa = 1;
	while(~scanf("%d %d", &n, &d)) {
		if(n == 0 && d == 0){
			break;
		}
		for(int i = 1; i <= n; i++) {
			double a, b;
			cin>>a>>b;
			nn[i].x= a;
			nn[i].y =b;
		}
		bool flag = true;
		for(int i = 1; i <= n; i++) {
			if(nn[i].y > d) {
				flag = false;
				break;
			}
			double a = nn[i].x;
			double b = nn[i].y;
			kk[i].fir = a - sqrt(d*d - b*b);
			kk[i].end = a + sqrt(d*d - b*b);
		}
		int ans = 1;
		if(!flag) {
			ans = -1;
		} else {
			sort(kk+1, kk + n+1, cmp);
			node tmp = kk[1];
			for(int i = 2; i <= n; i++) {
				if(kk[i].fir > tmp.end) {
					tmp = kk[i];
					ans++;
				} else if(kk[i].end < tmp.end) {
					tmp = kk[i];
				}
			}
		}
		cout<<"Case "<<caaa<<": "<<ans<<endl;
		caaa++;

	}


	return 0;
}