hiho一下第266周《剑刃风暴》题目分析

0
2

《剑刃风暴》题目分析

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

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

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

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

week266

我们只枚举其中一个在圆上的点,不妨叫这个点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)。

  • 有个问题,,按照题目的背景,圆心的坐标必须是整数吧,用极坐标表示的弧再求覆盖最多的点得到的是实数? 比如 2 2 0 0 3 3 这个测试用例里面应该是按照以上思路输出的是2吧? 但如果圆心坐标限制为整数的话输出会是1? 还不会解不知道是不是理解错题目了

  • 输入的是整数。但是并不要求圆心的坐标也是整数。

  • 添加评论
  • reply

0 answer(s)

write answer 切换为英文 切换为中文


转发分享