这是在研究所考题里面看到的 http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/103/103418.pdf 给定 n 个半径不完全相同的圆，要计算出总共有几个连通的区域。 如果所有的圆是给定的，那可以用plane-sweep法解决。 （不过我只能做到O((k + n) lg n)， k 是相交的圆的个数，不知道有没有 跟 k 无关的方法） 但是另一个问题是要求 incremental 计算，这部份有什麽特殊的资料结构 或是演算法可以使用吗？ 虽然可以用KD-tree来储存中心，但是这样就忽略了半径的资讯，有没有什麽trick？ --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 129.170.194.148 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1422643142.A.4E9.html