建立雷达

题面

一共有 n 个小岛位于 x 轴之上， x 轴为海岸， x 轴上方为海洋。现需要在海岸上建立雷达。在海岸建立的最少的雷达数目，使得雷达可以覆盖所有的小岛。可以认为每个小岛都是一 个点。如图所示，三个小岛分别是 P_1, P_2, P_3, 雷达的半径 d=2, 在 x 轴上建立两个雷达 (-2,0) 和 (1,0) 就能覆盖三个小岛。
一共有 n 个小岛位于 x 轴之上， x 轴为海岸， x 轴上方为海洋。现需要在海岸上建立雷达。在海岸建立的最少的雷达数目，使得雷达可以覆盖所有的小岛。可以认为每个小岛都是一 个点。如图所示，三个小岛分别是 P_1, P_2, P_3, 雷达的半径 d=2, 在 x 轴上建立两个雷达 (-2,0) 和 (1,0) 就能覆盖三个小岛。

输入

3 2
1 2
-3 1
2 1

1 2
0 2

0 0

输出

Case 1:2
Case 2:1

思路

处理出每一个小岛具海边为d的坐标，排序（按照做坐标从小到大）

代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;

const int N = 1010;

int n;
double d;
struct node {
	double x, y;
	double x1, x2;
}a[N];


bool cmp(node a, node b)
{
	if (a.x1 == b.x1)return a.x2 < b.x2;
	else return a.x1 < b.x1;
}

int main()
{
	int tt =  1,t = 0;
	while (cin >> n >> d && n)
	{
		for (int i = 1; i <= n; i++)
		{
			cin >> a[i].x >> a[i].y;
			if (d <a[i].y) {
				a[i].x1 = 0x3f3f3f3f;
				a[i].x2 = 0x3f3f3f3f;
				t++;
			}
			else {
				double l = sqrt(d * d - a[i].y * a[i].y);
				a[i].x1 = a[i].x - l, a[i].x2 = a[i].x + l;
			}
		}

		sort(a+1, a + 1 + n, cmp);

		int ans = 1;
		double now = a[1].x2;

		//cout << now << " " << endl;

		for (int i = 2; i <= n ; i++)
		{

		//	cout << now << " " <<a[i].x1<<" "<<a[i].x2<< endl;
			if (a[i].x1 == 0x3f3f3f3f)break;
			if (a[i].x1 <= now) { if (a[i].x2 < now) now = a[i].x2; }
			else {
				ans++;
				now = a[i].x2;
			}
		}


		if (t!=0)cout << "Case " << tt++ << ":" << -1 << endl;
		else cout << "Case " << tt++ << ":" << ans << endl;

	}

	return 0;

}