4. K11942 雷达安装

题目描述

假设海岸线是一个无限长的直线，陆地位于海岸线的一侧，另一侧是海洋。每个小岛可以看做是海洋中的一个点。在海岸线上安装的任何一个雷达能够覆盖的距离是d，所以如果小岛距离雷达的最大距离是d那么这个小岛就能够被雷达信号覆盖到。

我们使用笛卡尔坐标系，把海岸线看做是X轴，海洋在X轴的上方，陆地在X轴的下方，给出每个小岛在海洋中的位置，并给出雷达的覆盖范围，你的任务是编写程序计算出，如果覆盖所有的小岛至少需要安装多少个雷达。小岛的位置是用x、y坐标表示的。

输入格式

输入包含多组测试数据。对于每组测试数据：

第一行是两个整数n(1≤n≤1000)和d，分别表示小岛的数量n和雷达的覆盖范围d。

接下来n行，每行两个整数，分别表示每个小岛的位置的坐标。

每组测试用例之间用一个空行隔开，当输入为“0 0”时，表示输入结束

输出格式

对于每组测试用例，先输出测试用例的编号，然后输出需要安装的雷达的数量，如果无解输出-1 

样例：

输入样例：

3 2

1 2

-3 1

2 1

1 2

0 2

0 0

输出样例：

Case 1: 2

Case 2: 1

答案:

#include<bits/stdc++.h>
using namespace std;
double R;
int ans,n,d;
struct st{
	double l,r;
}s[1005];
double cmp(const st &x,const st &y){return x.r<y.r;}
int main(){
	int sum=0;
	while(cin>>n>>d&&n!=0&&d!=0&&++sum){
		int u=0;
		for(int i=1;i<=n;i++){
			int x,y;
			cin>>x>>y;
			int x1=y;
			if(x1<0) x1=-x1;
			if(x1>d)    {u=1;break;}
			s[i].l=x-sqrt(d*d-y*y);
			s[i].r=x+sqrt(d*d-y*y);
		}
		if(u!=0) 
		{cout<<"Case "<<sum<<": -1"<<endl;u=0;continue;}
		sort(s+1,s+n+1,cmp);
		R=s[1].r,ans=1;
		for(int i=2;i<=n;i++){
			if(R>s[i].l)continue;
			R=s[i].r,ans++;
		}
		cout<<"Case "<<sum<<": "<<ans<<endl;	
    }
	return 0;
}

最后

以上就是害羞黄豆为你收集整理的K11942 雷达安装样例：答案:的全部内容，希望文章能够帮你解决K11942 雷达安装样例：答案:所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。