bzoj#P3962. [WF2011]Coffee Central
[WF2011]Coffee Central
题目描述
这只是一时的狂热还是将长久地持续下去?你并不能肯定,不过在你家乡数目持续增长的咖啡馆着实成了一种风尚。显然,人们对于咖啡是如此地着迷以至于那些靠近更多咖啡馆的公寓需要更多的租金。
这引起了当地一家房地产公司的注意。他们对于根据靠近大量咖啡馆来确定城市当中最有价值的区域很感兴趣。他们给你了城市地图,标记了咖啡馆的位置。假定老百姓们只会为了早点走过一定数目的街区,你需要找到能到达最多咖啡馆的位置。就像你可能知道的那样,你的家乡是按照方格网的布局设计建造的,所以街区之间按南北和东西轴线对齐。 和 两个交叉口之间的距离是 。
输入格式
第一行四个整数 ,它们分别代表城市网格的面积为 ,咖啡馆的数量 ,以及询问个数 。
接下来 行每行两个整数 和 ;它们说明了第 个咖啡馆的位置,每个十字路口最多只有一个咖啡馆。
接下来 行每行包含了一个整数 ,表示人们为了咖啡会走过的最长距离。
多组数据,以 0 0 0 0
结束。
输出格式
对于测试数据的每个询问输出一行。
每行输出在给定的距离 以内可以抵达咖啡馆的最大数目,紧跟着输出最佳位置。
比如说样例输出说明了从最佳位置 出发,在询问要求的 的距离范围内可以抵达3个咖啡馆。
如果存在多个最佳位置,选择最南边的那个(也就是 坐标最小的),如果仍然多解,选择最西边的那个(也就是 坐标最小的)。
具体输出格式见样例。
4 4 5 3
1 1
1 2
3 3
4 4
2 4
1
2
4
0 0 0 0
Case 1:
3 (3,4)
4 (2,2)
5 (3,1)
数据规模与约定
对于 的数据,,,,,,。