ZOJ Problem Set – 2629 – Cover More Circles

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2629

又抽中一道要做两次变换的题。

化简后的题目差不多就是:用一个给定半径的圆去覆盖平面上的点集合,最多能覆盖多少点。

第一次变换比较明显。把大圆覆盖小圆的问题变换为圆的相交问题。这样问题就转化为找平面上被圆覆盖次数最多的点。
第二次变换有点微妙。一方面,虽然判断一个点被多少个圆覆盖非常简单,但在实数平面上的搜索还是不太现实的。另一方面,直接判断数个圆是否有公共交却相当复杂,即使只是3个圆的公共交。最终路线还是第一条(我在第二条上费时无数),但不是考虑平面上的任意点,而是考虑圆上的弧(一些情况下会收缩到点)。可以看到,能在平面的点上达到的最大覆盖数,同样也能在某一个圆上的弧上达到。于是算法的实现就是把圆上的弧按照该圆和其它圆的交点进行分割,然后找到被覆盖次数最大的那段。再在所有圆上取该值的最大便是结果了。

Advertisements
This entry was posted in ACM, Science. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s