首页 > 代码库 > [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;}
View Code

 

[noip2014day2-T1]无线网路发射器选址