从前有一个一望无际的海滩,海滩后面是陆地,前面是广阔的大海。海中有很多小岛(可以用一个点表示)。现在海滩上需要安装一些基站(海滩上的任意位置)这样岛上的居民就能用手机通话了,所有的基站的覆盖距离都是d,在距离d范围内的小岛都能收到基站发送的信号。
我们用笛卡尔坐标系来表示这个问题,定义x轴为海滩,x轴上方是大海,下方是陆地。现给出每个小岛的位置(用x-y坐标表示)和基站的覆盖范围d,你的任务就是写一个程序,计算出可以覆盖所有的小岛,至少需要在海滩上安装多少基站?
Input
输入包含多组数据。对每组数据,第一行包含两个整数n(1 <= n <= 1000)和d,n代表小岛数量,d代表基站的覆盖距离。接下来有n行,每行包含两个整数,表示小岛的位置坐标。输入n=0,d=0时退出。
Output
对每组数据,输出包含数据组数,格式如sample,后跟最少需要安装的基站数,如果无解,输出-1。
Sample Input
3 2
1 2
-3 1
2 1
1 2
0 2
1 -2
0 2
0 0
Sample Output
Case 1: 2
Case 2: 1
Case 3: -1
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
#define MAX 1001
struct stuPoint
{
int x;
int y;
};
struct stuLimit
{
double dFrom;
double dTo;
};
stuPoint stuIsland[MAX];
stuLimit stuDuan[MAX];
void vInput(int nN);
bool check(int nN,int nD);
void vSort(int nN);
bool bCmp(const stuLimit &stuA,const stuLimit &stuB);
void vPutOut(int nRet,int Case);
int nGetAns(int nN);
int main()
{
int nIslands,nDistance;
int ans;
int nCase;
nCase=1;
while(2==scanf("%d%d",&nIslands,&nDistance))
{
vInput(nIslands);
if((0==nIslands)&&(0==nDistance))
return 0;
if(check(nIslands,nDistance))
{
vSort(nIslands);
ans=nGetAns(nIslands);
}
else
ans=-1;
vPutOut(ans,nCase);
nCase++;
}
return 0;
}
void vInput(int nN)
{
int i;
for(i=1;i<=nN;i++)
{
scanf("%d%d",&stuIsland[i].x,&stuIsland[i].y);
}
}
bool check(int nN,int nD)
{
int i;
for(i=1;i<=nN;i++)
{
if(stuIsland[i].y>nD)
return false;
stuDuan[i].dFrom=stuIsland[i].x-sqrt(1.0*nD*nD-1.0*stuIsland[i].y*stuIsland[i].y);
stuDuan[i].dTo=stuIsland[i].x+sqrt(1.0*nD*nD-1.0*stuIsland[i].y*stuIsland[i].y);
}
return true;
}
void vSort(int nN)
{
sort(&stuDuan[1],&stuDuan[nN+1],bCmp);
}
bool bCmp(const stuLimit &stuA,const stuLimit &stuB)
{
return(stuA.dFrom<stuB.dFrom);
}
void vPutOut(int nRet,int Case)
{
printf("Case %d: %d\n",Case,nRet);
}
int nGetAns(int nN)
{
int i;
int ans;
int nTemp;
ans=1;
nTemp=stuDuan[1].dTo;
for(i=2;i<=nN;i++)
{
if(nTemp<stuDuan[i].dFrom)
{
nTemp=stuDuan[i].dTo;
ans++;
}
else
{
if(nTemp>stuDuan[i].dTo)
{
nTemp=stuDuan[i].dTo;
}
}
}
return ans;
}
分享到:
相关推荐
4G伪基站问题及影响分析.docx
这是一个用MATLAB编程来解决小区基站最优化选址问题的程序,有一定的实用性。
未执行本办法导致的基站中断 ,或是基站安全、运行问题引起的损失由责任部门承担。 第三章 职责 第三条 各部门职责划分 1.网络部职责: 1)、网络部为基站搬迁的职能主管部门。 2)、负责再次核实所申请搬迁及拆除...
移动通信基站网络覆盖问题 摘要 随着人均生活水平的不断提升,人们对于移动通信技术水平的要求也在不断提高,移动通信基站的覆盖问题也成了热点研究问题之一。 本文主要研究移动通信基站的覆盖问题,即可将其转化...
随着我国电信行业重组的进一步深化,电信运营商全业务运营是大势所趋,由于运营商重组方案尚末公布,因此本文只针对利用现有的固定网络资源对移动基站接入进行探讨。 1 固网接入层资源十分丰富 由于我国固定...
问题二,根据题目中给定的10组TOA测量数据和所有基站的三维坐标(对应附录中编号为case011_input.txt到case020_input.txt的文件),首先使用问题一中的模型求解出终端坐标,再根据基站之间的距离进行基站的精简,再...
基站问题 低功耗、即插即用能力的小基站 超密集组网的主要问题 超密集组网的关键技术 什么是超密集组网 超密集组网的部署模式 多连接技术 多连接技术的主要目的在于实现UE (用户终端)与宏微多个无线网络节点的同时...
在调试packet abis 时候碰到下面5个问题 描述:基站侧IP已经配置,BSC 从BCSU无法ping 通BTS IP....解决方案:下电重启基站问题解决。 描述:从BCSU 能ping BTS IP和CP GW, 从ETPE能 ping CP GW,但不能ping BTS IP.
5G热点问题详解系列——基站滤波器.pdf
pso算法最优化计算区域覆盖问题节点基站电信
2) 交叉代维:由于铁塔公司基站资源历史由来原因,维护时将会有移动、 电信、联通原班代维人员进行维护,交叉管理问题凸显。 3)数量众多:一个地市的基站少则数百个,多则数千个,整个通信行业基 站数量超过 300 ...
基站问题:Gnb收到Msg5后处理异常,没有上发Initial UE Message,此种情况建议提单处理; 传输问题:NG口SIG建立或上下文建立流程中,出现传输中端导致流程失败,此种情况需要联合传输处理; NAS过程异常:NAS过程...
对于从事基站维护的相关工作人员,有很大帮助!
华为杯”第十三届全国研究生数学建模竞赛-基于无线通信基站的室内三维定位问题:三维定位的MATLAB算法,包含源代码,测试结果,误差分析全套
皮基站是开发的一款面向中小企业市 场TD-LTE 制式毫微蜂窝基站。通过现有的多种 Internet 接入手段可迅速便捷 地将 TD-LTE 网络布设到任何一个需要的站点,实现与 TD -LTE 宏网相似的数据、 语音通信能力,以解决 TD...
7、常见的基站问题:1、基站基站亮红色灯,但是软件可以搜索到。原因可能是:基站ID号错误、电脑防火墙没关、基站服务器IP错误、网络不通畅、端口被占用(概率较低)等。 天地伟业技术培训资料全文共17页,当前为第...
基站天线是移动通信系统的重要组成部分,其质量的好坏直接影响整个无线网络的整体性能,只有天线质量得到有效控制,网络质量才有
4G基站设备安装要点及常见问题处理 4G基站设备安装要点及常见问题处理
华为TD基站常见问题排查手册.pdf华为TD基站常见问题排查手册.pdf华为TD基站常见问题排查手册.pdf华为TD基站常见问题排查手册.pdf华为TD基站常见问题排查手册.pdf华为TD基站常见问题排查手册.pdf华为TD基站常见问题...
WiMAX基站与IMT-2000基站间干扰共存研究,孙慧,,本文主要研究了WiMAX系统基站与IMT-2000系统基站间的干扰共存问题,采用确定性计算方法研究两系统基站间的邻频干扰。在干扰分析的基��