首页 > 代码库 > [noip2014day2-T1]无线网路发射器选址
[noip2014day2-T1]无线网路发射器选址
随着智能手机的日益普及，人们对无线网的需求日益增大。某城市决定对城市内的公共场所覆盖无线网。
假设该城市的布局为由严格平行的129条东西向街道和129条南北向街道所形成的网格状，并且相邻的平行街道之间的距离都是恒定值 1。东西向街道从北到南依次编号为0,1,2…128,南北向街道从西到东依次编号为 0,1,2…128。
东西向街道和南北向街道相交形成路口，规定编号为 x 的南北向街道和编号为 y 的东西向街道形成的路口的坐标是（x, y）。在某些路口存在一定数量的公共场所。
由于政府财政问题，只能安装一个大型无线网络发射器。该无线网络发射器的传播范围是一个以该点为中心，边长为 2*d 的正方形。传播范围包括正方形边界。
例如下图是一个 d = 1 的无线网络发射器的覆盖范围示意图。 
现在政府有关部门准备安装一个传播参数为 d 的无线网络发射器，希望你帮助他们在城市内找出合适的路口作为安装地点，使得覆盖的公共场所最多。
#include<iostream>#include<cstring>#include<cstdio>#include<cstdlib>#include<algorithm>#include<iomanip>#include<map>#include<set>#include<vector>#include<ctime>#include<cmath>#define LL long long using namespace std;#define LL long long #define up(i,j,n) for(int i=(j);(i)<=(n);(i)++)#define max(x,y) ((x)<(y)?(y):(x))#define min(x,y) ((x)<(y)?(x):(y))#define FILE "1"const int maxn=30,inf=1000000000;int read(){ int x=0;bool flag=0;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)flag=1;ch=getchar();} while(ch<=‘9‘&&ch>=‘0‘){x=x*10+ch-‘0‘;ch=getchar();} return flag?-x:x;}int d,n,x[maxn],y[maxn],k[maxn];int Max=0,Num=0;int main(){ d=read(),n=read(); up(i,1,n)x[i]=read(),y[i]=read(),k[i]=read(); up(i,0,128)up(j,0,128){ int sum=0; up(e,1,n)if(x[e]>=i-d&&x[e]<=i+d&&y[e]>=j-d&&y[e]<=j+d)sum+=k[e]; if(sum==Max)Num++; if(sum>Max)Max=sum,Num=1; } printf("%d %d\n",Num,Max); return 0;}
[noip2014day2-T1]无线网路发射器选址
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。