题目名称	1806. [NOIP 2014]无线网路发射器选址
输入输出	`wireless.in/out`
难度等级	★
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	cqw 于2014-11-12加入
开放分组	全部用户
提交状态
分类标签	NOIP/CSP 基本
	分享题解

通过：391，提交：931，通过率：42%
Regnig Etalsnart	100	0.000 s	0.00 MiB	C++
Youngsc	100	0.000 s	0.00 MiB	C++
Harry Potter	100	0.000 s	0.00 MiB	C++
Fabio_Grosso	100	0.000 s	0.00 MiB	C++
ignitedark	100	0.000 s	0.00 MiB	C++
Eddy2008	100	0.000 s	0.00 MiB	C++
cy	100	0.000 s	0.08 MiB	C++
QHY256	100	0.001 s	1.98 MiB	C++
lyqlyqcogs	100	0.002 s	0.38 MiB	C++
Samle	100	0.002 s	0.38 MiB	C++

本题关联比赛
图论练习和一些常规题
图论练习和一些常规题
暑假综合模拟2

关于无线网路发射器选址的近10条评论(全部评论)
大水题WA了三次QAQ，身败名裂 Hallmeow 2017-11-07 10:24 28楼
作死拿二维前缀和做，调了一个多小时......身败名裂胡嘉兴 2017-10-27 07:15 27楼
1 2 4 4 10 6 6 20 拿走不谢，你们帮忙打其他题就好雷yh 大傻逼据说这是zzy 2017-10-23 21:23 26楼
H_Lost 2017-10-07 18:01 25楼
数组开小了一个，大水题调了30分钟....身败名裂........ fate1 2017-05-25 20:02 24楼
kZime 2016-12-11 15:11 23楼
第一个用vscode写的题（嗯？ Rapiz 2016-11-06 20:48 22楼
这题用了逆向思维，大概30分钟完成，留个名，我也曾是榜上第一。。。 O(∩_∩)O哈哈~ Zwoi_只会打表抄代码的蒟蒻 2016-11-06 18:14 21楼
zeppoe 2016-11-02 13:08 20楼
为何不直接暴力搜索过呢？啊哈哈，虽然时间超级慢，但是毕竟最好想呢雪 2016-10-26 21:15 19楼

1806. [NOIP 2014]无线网路发射器选址

★ 输入文件：wireless.in 输出文件：wireless.out 简单对比
时间限制：1 s 内存限制：128 MiB

【题目描述】

随着智能手机的日益普及，人们对无线网的需求日益增大。某城市决定对城市内的公共场所覆盖无线网。

假设该城市的布局为由严格平行的129条东西向街道和129条南北向街道所形成的网格状，并且相邻的平行街道之间的距离都是恒定值 1。东西向街道从北到南依次编号为0,1,2…128,南北向街道从西到东依次编号为 0,1,2…128。

东西向街道和南北向街道相交形成路口，规定编号为 x 的南北向街道和编号为 y 的东西向街道形成的路口的坐标是（x, y）。在某些路口存在一定数量的公共场所。

由于政府财政问题，只能安装一个大型无线网络发射器。该无线网络发射器的传播范围是一个以该点为中心，边长为 2*d 的正方形。传播范围包括正方形边界。

例如下图是一个 d = 1 的无线网络发射器的覆盖范围示意图。

现在政府有关部门准备安装一个传播参数为 d 的无线网络发射器，希望你帮助他们在城市内找出合适的安装地点，使得覆盖的公共场所最多。

【输入格式】

第一行包含一个整数 d，表示无线网络发射器的传播距离。

第二行包含一个整数 n，表示有公共场所的路口数目。

接下来 n 行，每行给出三个整数 x, y, k, 中间用一个空格隔开，分别代表路口的坐标(x, y)以及该路口公共场所的数量。同一坐标只会给出一次。

【输出格式】

输出一行，包含两个整数，用一个空格隔开，分别表示能覆盖最多公共场所的安装地点方案数，以及能覆盖的最多公共场所的数量。

【样例输入】

【样例输出】

1 30

【数据规模与约定】

对于100%的数据，$1\leq d\leq 20,1\leq n\leq 20,0\leq x\leq 128,0\leq y\leq 128,0<k\leq 1,000,000$。

【来源】

NOIP2014 Day2 Task1