POJ1328 Radar Installation
程序员文章站
2022-03-26 14:04:28
...
题意:
x轴是海岸线,x轴上方是海洋,海洋中有n个岛屿,给定每个岛屿的坐标,当一个雷达到岛屿的距离不超过d时,认为该雷达覆盖了该岛屿,雷达只能放在x轴上,问至少需要多少个雷达才可以覆盖全部岛屿
思路:
对每个岛屿P,算出覆盖它的雷达,必须位于x轴上的区间[Ps,Pe],将问题转换为区间选点问题求解。
做这道题的时候憨憨了.....在输入部分直接判断了是否为可行解,然后输出-1跳出........
代码实现:
#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;
}
上一篇: 基于注解的IOC配置
推荐阅读
-
AndroidStudio更新时报错:Connection Error,Temp directory inside installation
-
Realcase: Failed to upgrade SQL Server 2016 SP2 CU11. (Installation success or error status: 1648)
-
Ubuntu安装telent服务器时出现:apt-get:Package has no installation的原因及解决方法
-
The packaging and installation process of Android programs
-
[转发] Apache SSL Certificate Installation
-
Rails4 Web installation
-
Rails4 Web installation
-
kali遇到“已安装的 post-installation 脚本 返回了错误的问题的解决
-
使用IntelliJ IDEA导入 Flink 消费kafka报错 Error: A JNI error has occurred, please check your installation an
-
Installation failed with message Failed to establish session.