欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ1328 Radar Installation

程序员文章站 2022-03-26 14:04:28
...

题意:

x轴是海岸线,x轴上方是海洋,海洋中有n个岛屿,给定每个岛屿的坐标,当一个雷达到岛屿的距离不超过d时,认为该雷达覆盖了该岛屿,雷达只能放在x轴上,问至少需要多少个雷达才可以覆盖全部岛屿

POJ1328 Radar Installation

 


思路:

对每个岛屿P,算出覆盖它的雷达,必须位于x轴上的区间[Ps,Pe],将问题转换为区间选点问题求解。

做这道题的时候憨憨了.....在输入部分直接判断了是否为可行解,然后输出-1跳出........

POJ1328 Radar Installation


代码实现:
 

#include <iostream>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;

struct section{
	double a;
	double b;
	section(){}
	section(double aa,double bb):a(aa),b(bb){}
	friend bool operator<(const section &s1,const section &s2){
		if(s1.b!=s2.b)
			return s1.b<s2.b;
		else
			return s1.a>s2.a;
	}
};

int n,d,ans;
double p,q;
section s[1010];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
//	freopen("in.txt","r",stdin);
  //  freopen("output.txt","w",stdout);
	int count=0;
	while(cin>>n>>d){
		if(n==0&&d==0)
			break;
		count++;
		ans=0;
		bool flag=true;
		if(d<=0)
			flag=false;	
		for(int i=0;i<n;i++){
			cin>>p>>q;
			double dis=sqrt(d*d-q*q);
			if(fabs(q)>d||q<0)
				flag=false;
			s[i].a=p-dis;
			s[i].b=p+dis;
		}
		if(flag){
			sort(s,s+n);
			ans=1;
			double cursor=s[0].b;
			for(int i=1;i<n;i++){
				if(s[i].a>cursor){
					ans++;
					cursor=s[i].b;
				}
			}
			cout<<"Case "<<count<<": "<<ans<<endl;
		}
		else
			cout<<"Case "<<count<<": "<<-1<<endl;
	}
	return 0;
}

 

相关标签: 贪心算法