雷达设备

假设海岸是一条无限长的直线，陆地位于海岸的一侧，海洋位于另外一侧。

每个小岛都位于海洋一侧的某个点上。

雷达装置均位于海岸线上，且雷达的监测范围为 $d$，当小岛与某雷达的距离不超过 $d$ 时，该小岛可以被雷达覆盖。

我们使用笛卡尔坐标系，定义海岸线为 $x$ 轴，海的一侧在 $x$ 轴上方，陆地一侧在 $x$ 轴下方。

现在给出每个小岛的具体坐标以及雷达的检测范围，请你求出能够使所有小岛都被雷达覆盖所需的最小雷达数目。

输入格式

第一行输入两个整数 $n$ 和 $d$，分别代表小岛数目和雷达检测范围。

接下来 $n$ 行，每行输入两个整数，分别代表小岛的 $x，y$ 轴坐标。

同一行数据之间用空格隔开。

输出格式

输出一个整数，代表所需的最小雷达数目，若没有解决方案则所需数目输出 $−1$。

数据范围

$1≤n≤1000$,
$−1000≤x,y≤1000$

输入样例：

3 2
1 2
-3 1
2 1

输出样例：

2

题目解析

陆地很大，很明显有个最优方法就是将雷达放到陆地和海洋的交界线上，这样就将一个二维的情况转化成了一维。

但是这样的线上又有很多的点，而岛的数量是有限的，所以我们可以从岛的坐标入手。

如何将岛和交界线的关系连接起来？

我们发现，如果以每个岛为圆心，画一个圆，那么就一定会和交界线有交点（如果不存在，那么直接输出 -1），如果是两个交点，那么在这两个交点之间的任何位置建造雷达都能够探测到岛的位置。这两个点很好求，知道圆的半径和圆心距离交界线的长度 y ，通过勾股定理就可以计算出交点的位置（如果 d == r，那么就只有一个交点）。

这样我们就转化成了在直线上找最少的点，使每个区间内都能有一个点的问题。

我们按照坐标从小到大进行排序，每次记录当前区间的右区间，若当前坐标的左区间比记录的右区间还要大，那么就可以新建一个点，并且更新当前记录的右区间。

#include <cmath>
#include <cstdio>
#include <algorithm>

const int N = 1005;
struct Location {
	double x, y;
} cur[N];

bool cmp(Location x, Location y) {
	if(x.y == y.y) return x.x < y.x;
	else return x.y < y.y;
}

int main() {
	int n, d; bool success = true;
	scanf("%d %d", &n, &d);
	for (int i = 1; i <= n; i++) {
		double x, y;
		scanf("%lf %lf", &x, &y);
		if(y > d) {
			success = false;
			break;
		}
		
		cur[i].x = (double)(x - sqrt((d * d) - (y * y)));
		cur[i].y = (double)(x + sqrt((d * d) - (y * y)));
	}
	
	if(!success) {
		puts("-1");
		return 0;
	}
	
	std::sort(cur + 1, cur + 1 + n, cmp);
	
	int ans = 0; double last = -1e9;
	for (int i = 1; i <= n; i++) {
		if(i == 1) { ans++; last = cur[i].y; }
		else {
			if(cur[i].x > last) {
				ans++;
				last = cur[i].y;
			}
		}
	}
	
	printf("%d\n", ans);
	return 0;
}