正文索引 [隐藏]

传送门

题目大意

假设海岸是一条无限长的直线。陆地在海岸的一边，海洋在另一边。每个小岛都是位于海边的一个点。而任何位于海岸线上的雷达装置，只能覆盖d距离。所以如果小岛与一个雷达之间的距离最多为d，那么它可以被这个雷达覆盖。 我们使用笛卡尔坐标系，定义海岸是x轴，海边在x轴上方，陆地在下方。给定海洋中每个岛屿的位置，给定雷达装置覆盖的距离，你的任务是编写一个程序，找到覆盖所有岛屿的最小数量的雷达装置。请注意，岛屿的位置由其(x,y)坐标表示。如果无法完成覆盖，则输出“-1”。

思路

给定覆盖半径与一系列散点，问最少用多少雷达可以覆盖到所有小岛。

很明显是一个贪心问题。在思考贪心策略之前我们需要考虑一下输出“-1”的情况。首先，因为雷达只能装在岸边，所以如果至少存在一个点，它距岸边的距离大于雷达半径，显然就无法完成覆盖了。其次，数据中存在d<0的情况，这种情况也是输出-1.

接下来思考贪心。要让雷达尽可能少，那就要让每个雷达尽可能的多覆盖小岛。如何去判断多个小岛能否被同一个雷达覆盖就成了这道题的核心问题。

以每个岛屿为圆心，d为半径做一个新圆，圆与x轴相交的两点会构成一个区间。不难想到，如果任意两个岛屿的区间存在重合，那么它们就能被同一个雷达覆盖。

所以对每个岛屿计算出它的区间值，以左边界为关键字排序，然后去判断就行了。

代码

#include <cmath>
#include <cstdio>
#include <vector>
#include <utility>
#include <iostream>
#include <algorithm>

#define PAIR pair<double, double>

using namespace  std;

const int N = 1010;

int n, d, cnt;

class Node {
public:
	int x, y;
	PAIR sec;

	void calcSec() {
		double tmp = sqrt((d * d) - (y * y));
		sec = make_pair(x - tmp, x + tmp);
	}
}node[N];

static bool cmp(Node& a, Node& b) {
	return a.sec.first < b.sec.first;
}

int main() {
	while(scanf("%d%d", &n, &d)) {
		if(n == 0 && d == 0) break;
		cnt++;
		if(d < 0){
			printf("Case %d: -1\n", cnt);
			continue;
		}

		int ans = 0;
		for(int i = 0; i < n; i++) {
			scanf("%d%d", &node[i].x, &node[i].y);
			if(abs(node[i].y) > d) {
				printf("Case %d: -1\n", cnt);
				continue;
			}
			node[i].calcSec();
		}
		sort(node, node + n, cmp);

		PAIR curSec = node[0].sec; ans += 1;
		for(int i = 1; i < n; i++) {
			if(node[i].sec.first < curSec.second) continue;
			else {
				curSec = node[i].sec;
				ans++;
			}
		}

		printf("Case %d: %d\n", cnt, ans);

	}
}