题目传送门: POJ 1328

给一个平行与 x 轴的海岸线，y < 0 部份为土地，y > 0部份为海，在海上有小岛，小岛的坐标给出，现在在海岸线上装雷达，雷达的覆盖范围为半径为 d 的圆，求最少要多少雷达能够覆盖所有岛，若是无法覆盖所有的岛，输出 -1 。

具体来说，先以 x 坐标排序，对于一个岛，求出可以覆盖它的雷达的位置在 x 轴上的范围，若两可检测的两小岛的雷达范围有重叠，则两小岛可公用一个雷达检测，最后用贪心来求雷达的最小数量就行。

若小岛的 y 坐标大于雷达的半径，就无法检测到了。

###Code

POJ 1328
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//By Brickgao
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define eps 1e-8
using namespace std;

typedef struct record{
	int x;
	int y;
	double left;
	double right;
} record;

record rec[1010];

bool cmp(record tmp1, record tmp2)
{
	return tmp1.x < tmp2.x;
}

int main()
{
	int n, d, cas = 0, ans;
	bool flag;
	while(~scanf("%d%d", &n, &d) && !(n == 0 && d == 0))
	{
		flag = false;
		cas ++;
		for(int i = 0; i < n; i ++)
		{
			scanf("%d%d", &rec[i].x, &rec[i].y);
			double tmp = sqrt(d * d - rec[i].y * rec[i].y);
			rec[i].left = rec[i].x - tmp;
			rec[i].right = rec[i].x + tmp;
			if(rec[i].y > d) flag = true;
		}
		printf("Case %d: ", cas);
		if(flag)
			printf("-1\n");
		else
		{
			ans = 0;
			sort(rec, rec + n, cmp);
			double left = rec[0].left;
			double right = rec[0].right;
			for(int i = 1; i < n; i++)
			{
				if(right > rec[i].left - eps)
				{
					left = rec[i].left;
					if(right > rec[i].right + eps)
						right = rec[i].right;
				}
				else
				{
					ans ++;
					left = rec[i].left;
					right = rec[i].right;
				}
			}
			printf("%d\n", ans + 1);
		}
	}
    return 0;
}