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

Question

假设有一幅二维地图，地图上有n个坐标（X0,Y0）...(Xn,Yn)，现在要投掷一颗炸弹，炸弹的有效攻击范围为一个矩形区域（长为w，宽为h），要求要炸中最多的坐标。
我知道遍历可以解决问题（算法复杂度为n^2），但是有没有更高效的算法呢？
P.S.其实我本意是要解决一个裁切图片的问题，图片现在能分析出特征点，我要截取一个固定面积的矩形区域，要求这个区域包含最多的特征点。只是觉得用以上方式问会容易理解一点。

Answer 1

题主请速看你的评论。这个问题和POJ2482是完全等同的，你可以去直接查找解题报告。朴素遍历我觉得达不到O(n^2)的复杂度，因为你不能假定任何一个目标都在矩形的角点上。事实上POJ给出的范围niandX[k]

Answer 2

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