POJ 1328

题目翻译

假设滑行是一条无限长的直线。陆地在海岸线的一边，海洋在另一边。每个小岛都是位于海边的一个点。而任何位于海岸上的雷达装置只能覆盖 d 距离，因此，如果它们之间的距离不超过 d，那么海上的岛屿可以被半径装置覆盖。

我们使用笛卡尔坐标系，将滑行定义为 x轴。海在 x轴上方，陆在 x轴下方。考虑到每个岛屿在海上的位置，以及雷达装置的覆盖距离，您的任务是编写一个程序，以找到覆盖所有岛屿的雷达装置的最小数量。请注意，岛的位置由其 x-y 坐标表示。

输入

输入由几个测试用例组成。每种情况的第一行包含两个整数 n（1<=n<=1000）和 d，其中 n 是海上岛屿的数量，d 是雷达装置的覆盖距离。然后是 n 行，每行包含两个整数，表示每个岛位置的坐标。然后，一个空白行将案例分开。

输入端由包含一对零的行终止。

输出

对于每个测试用例输出，一行由测试用例编号和所需的最小雷达安装数量组成。“-1”安装意味着在这种情况下没有解决方案。

样例

输入

3 2
1 2
-3 1
2 1

1 2
0 2

0 0

输出

Case 1: 2
Case 2: 1

解题思路

只能在 x 轴上安装雷达，可以观察半径为 d 的圆内的小岛，我们可以以这个小岛的坐标所在x轴呈现的圆的原点进行排序，这样排序后，只需遍历一次，比较小岛跟当前雷达的位置，不能覆盖就把数量++，然后找新雷达的位置，如果找不到就输出“-1”

代码示例

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;

int n,m;
int tim=1;

struct island{
	double x;
	double y;
}a[100010];

double dis(const island a,const island b){
	return (a.x-b.x)*(a.x-b.x)+(b.y*b.y);
}

bool cmp(island a,island b){
	double len_1=a.x+sqrt(m*m*1.0-a.y*a.y);
	double len_2=b.x+sqrt(m*m*1.0-b.y*b.y);
	return len_1<len_2;
}

int main(){
	while(cin>>n>>m){
		if(n==0&&m==0) break;
		bool ok=0;
		for(int i=1;i<=n;i++){
			cin>>a[i].x>>a[i].y;
			if(a[i].y>m*1.0) ok=1;
		}
		sort(a+1,a+1+n,cmp);
		cout<<"Case "<<tim<<": ";
		tim++;
		if(ok==1) cout<<"-1"<<endl;
		else{
			island now;
			now.x=a[1].x+sqrt(m*m*1.0-a[1].y*a[1].y);
			now.y=0;
			int sum=1;
			for(int i=2;i<=n;i++){
				if(dis(now,a[i])<=m*m*1.0) continue;
				else{
					sum++;
					now.x=a[i].x+sqrt(m*m*1.0-a[i].y*a[i].y);
				}
			}
			cout<<sum<<endl;
		}
	}
	return 0;
}