摘要: 強烈推薦此題！
先考察一下這個問題的性質。
性質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)。
閱讀全文