摘要: 强烈推荐此题！
先考察一下这个问题的性质。
性质1：任何一个圆都覆盖了一个闭区域。
性质2：对于任意一个点，覆盖它的最上面的那个圆，一定是可见的。
性质3：如果一个圆不可见（它被完全覆盖），那么它的边界是被完全覆盖的。
性质4：n个圆最多有2(n-1)^2个交点，这些交点把n个圆分成最多2(n-1)^2条小圆弧。
性质5：对于每个小圆弧，要么它全被覆盖，要么它全不被覆盖。
根据性质1和性质2，问题转化为恰当地找出一些点，对于每个点，把覆盖它的最上面的圆标记为可见。
根据性质3，这些点一定在所有圆的边界集合内。
根据性质5，所有小圆弧构成边界集合。每个小圆弧上只要任意取一个点就能代表整个小圆弧（边界）。不妨取中点。
至此得到算法：取所有小圆弧的中点，对每个点找到覆盖它的最上面的圆。
根据性质4，最多取2(n-1)^2个点。对每个点找到覆盖它的最上面的圆，需要O(n)次运算。总复杂度是O(n^3)。
阅读全文