《剑刃风暴》题目分析

本题是一道非常经典的计算几何题目，可以抽象成这样一个问题：给定平面上N个点，用一个半径为R的圆最多可以覆盖其中几个点？

我们知道半径确定的情况下，2个(在圆上)的点可以确定一个圆。所以我们可以枚举2个在圆上的点，确定圆心，然后统计这个圆一共包含多少个点。在所有枚举的圆中取包含点数最多的圆。

这个算法哪里都好，就是复杂度太高，是O(N^3)的，不能通过所有的数据。

更优的算法是如下的O(N^2logN)的算法：

我们只枚举其中一个在圆上的点，不妨叫这个点A。那么圆心的位置处于以A为圆心，半径为R的圆周上，如图所示。

我们考虑其中哪个圆能覆盖最多的点。

对于A以外的任意一个点B，如果B到A的距离大于2R，那么显然任意覆盖A的圆都覆盖不到B。

否则，以B为圆心，R为半径作圆，设圆B与圆A相交于PQ两点，如图所示。那么显然圆心在PQ这段弧的圆都能覆盖点B。

我们可以把PQ这段弧看作在圆周上的一段区间，可以用一个极角区间表示[a, b]，其中a是P的极角，b是Q的极角。

每一个距离A不超过2R的点B都对应这样一个区间。我们要找覆盖点最多的圆，就转化成了找被区间覆盖次数最多的点。

给定N个区间，找被覆盖次数最多的点也是一个经典问题。可以把区间端点排序之后扫描解决。复杂度O(NlogN)。

综上所述，对于确定的A，可以O(NlogN)解决。那么我们枚举所有的点当作A，再按上述算法处理，总时间复杂度是O(N^2logN)。