3406 - 无线网络发射器选址
随着智能手机的日益普及，人们对无线网的需求日益增大。某城市决定对城市内的公共
场所覆盖无线网。
假设该城市的布局为由严格平行的129条东西向街道和129条南北向街道所形成的网格
状，并且相邻的平行街道之间的距离都是恒定值1。东西向街道从北到南依次编号为
0,1,2…128,南北向街道从西到东依次编号为0,1,2…128。
东西向街道和南北向街道相交形成路口，规定编号为x的南北向街道和编号为y的东西
向街道形成的路口的坐标是（x, y）。 在 某 些 路 口 存 在 一 定 数 量 的 公 共 场 所 。
由于政府财政问题，只能安装一个大型无线网络发射器。该无线网络发射器的传播范围
是一个以该点为中心，边长为2*d的正方形。传播范围包括正方形边界。
例如下图是一个d = 1的无线网络发射器的覆盖范围示意图。
现在政府有关部门准备安装一个传播参数为d的无线网络发射器，希望你帮助他们在城
市内找出合适的安装地点，使得覆盖的公共场所最多
题目输入
输入文件名为wireless.in。
第一行包含一个整数d，表示无线网络发射器的传播距离。
第二行包含一个整数n，表示有公共场所的路口数目。
接下来n行，每行给出三个整数x, y, k, 中间用一个空格隔开，分别代表路口的坐标(x, y)
以及该路口公共场所的数量。同一坐标只会给出一次
题目输出
输入/输出样例
题目输入
1 2 4 4 10 6 6 20
题目输出
1 30
提示
【数据说明】
对于100%的数据，1 ≤ d ≤ 20，1 ≤ n ≤ 20， 0 ≤ x ≤ 128, 0 ≤ y ≤ 128, 0 < k ≤
1,000,000。
C++解答
#include <cstdio> int d , n , x , y , k ; int g[130][130] = {0} ; int ans = -1 , cnt = 0 ; int xl , xr , yl , yr , i , j ; void draw() { xl = x-d ; if (xl < 0) xl = 0 ; xr = x+d ; if (xr > 128) xr = 128 ; yl = y-d ; if (yl < 0) yl = 0 ; yr = y+d ; if (yr > 128) yr = 128 ; for (i = xl ; i <= xr ; i ++ ) for (j = yl ; j <= yr ; j ++ ) g[i][j] += k ; } int main() { // freopen("wireless.in" ,"r",stdin ) ; // freopen("wireless.out","w",stdout) ; int p ; scanf("%d%d", &d , &n ) ; for (p = 0 ; p < n ; p ++ ) { scanf("%d%d%d", &x , &y , &k ) ; draw() ; } for (i = 0 ; i <= 128 ; i ++ ) { for (j = 0 ; j <= 128 ; j ++ ) { if (g[i][j] > ans) { ans = g[i][j] ; cnt = 1 ; } else if (g[i][j] == ans) cnt ++ ; } } printf("%d %d\n", cnt , ans ) ; fclose(stdin ) ; fclose(stdout) ; return 0 ; }
提示
【数据说明】
对于100%的数据，1 ≤ d ≤ 20，1 ≤ n ≤ 20， 0 ≤ x ≤ 128, 0 ≤ y ≤ 128, 0 < k ≤
1,000,000。