投一颗炸弹，要炸中地图上尽可能多坐标，有什么高效的算法

Question

假设有一幅二维地图，地图上有n个坐标（X0,Y0）...(Xn,Yn)，现在要投掷一颗炸弹，炸弹的有效攻击范围为一个矩形区域（长为w，宽为h），要求要炸中最多的坐标。

我知道遍历可以解决问题（算法复杂度为n^2），但是有没有更高效的算法呢？

P.S.其实我本意是要解决一个裁切图片的问题，图片现在能分析出特征点，我要截取一个固定面积的矩形区域，要求这个区域包含最多的特征点。只是觉得用以上方式问会容易理解一点。

Answer 1

题主请速看你的评论。这个问题和POJ 2482是完全等同的，你可以去直接查找解题报告。

朴素遍历我觉得达不到O(n^2)的复杂度，因为你不能假定任何一个目标都在矩形的角点上。

事实上POJ给出的范围n<=10000就是照着O(n^2)或接近的复杂度来的，绝对不是要求在O(nlogn)左右解决。

例如四个点如果在(0,1) (0,-1) (-1,0) (1,0)，目标区域为2*2，则此时最优解为4。但如果把任何一个目标当作角点，无论向哪个方向扩展，都会得到错解3。你可以画一画这个图，非常显然。

---

遍历是跑不了的，不过谁说遍历非要O(n^2)呢？

对于线段的区间查询用线段树，对于矩形的子矩形查询用二维线段树。

预处理

1. 离散化处理。先只审查X坐标。
2. 把所有点的X坐标排序，形成有序列表X[0]...X[i]，O(nlogn)。
3. 记录每个X[i]到最近的下一个X坐标X[i+1]的距离。相同就记0，没关系。
4. 扫描从每个X[i]开始，向右延伸h的距离，最远能覆盖到的坐标位置k（即max(k) within {k>i and X[k]<=X[i]+h}）。注意用左右双下标线性前推，这个扫描是O(n)的可不是O(n^2)。
5. 对Y坐标重复以上的步骤。

最后将X和Y轴，都归约成[0, 1, ... , n-1]这样的元素数量为n的线性整数区间。至于各个点之间的X、Y轴距离，被记录到了每个点的权值，成为了一种附加数据。

线段树和二维线段树

线段树就是把区间不断二分形成一个二叉树。每一个节点代表一个区间，左子树和右子树，是将这个区间一分为二的结果，合并起来等同于父亲节点的区间。在线段树上，查询任意一个区间，都是最优O(logn)的。

离散化处理的意义就在于，忽略一切坐标之间长长短短的差异，将坐标“平均化”成若干个元素。这样在建树的时候，就可以完全避免不平衡状况，不会造成二叉树查询的退化，时间复杂度保证最优。

只要分开审查X和Y两个维度，就可以把线段树扩展到二维。

二维线段树的简单想法，就是二叉树套二叉树。用线段树负责一个维度，线段树的每一个节点里再建立一个二叉树，负责另一个维度。这样查询任意一个矩形范围，都是O(logn*logn)的。

---

剩下的算法就略了，二维线段树的算法是现成的。如果我没弄错，那么总体复杂度是O(n^2*(logn)^2)的，感谢评论指正。

Answer 2

很感谢 @沙渺 和 Zhenbo Li提供的思路。搜索"poj 2482"或者"stars in your window"的确有解决的办法。

其实我的原意是要解决一个裁切图片的问题，我的图片经过Open SURF算法能够得到一组特征坐标的数组（特征点没有权值），接下来就要截取一个矩形区域，这个区域应该覆盖尽可能多的特征点。后来转换了一下思路，其实妥协一下就能很简单地解决这个问题，我把图片resize为和矩形区域一样的宽度或者高度，再去获取特征坐标，接下来就只剩求一个维度的上的最大区间问题了。

Answer 3

• -# 为什么认为这就是指定中心点获半径X的圆范围内点的问题？