※ 引述《bleed1979 (十三)》之铭言： : ※ 引述《tkcn (小安)》之铭言： : : 一条边的中垂线上任何一点，都与两个顶点距离相等， : : 三角形的外心则是三边中垂线的交点，同时也是外接圆的圆心， : : 自然和三角形顶点距离都相同。 : : 跟 convex null 似乎倒是没什麽关系， : : 而且很容易可以找到一个反例， : : 想像一个 convex hull 中间密密麻麻塞满了点，只有中心位置有一块空白。 : : 很明显这块空白就是最大圆，但他不会接触到任何 convex hull 上的点。 : 感谢您的回应， : 然而，我的原文指的是convex hull任意不照顺序的三点所构成三角形， : (我原文少讲了任意，造成你的误解真抱歉) : 这个三角形的外心有可能落在你讲的中心位置。 呃不知道我有没有误会你的意思... 那例如底下的测资，4个点: (-4,-3) (4,-3) (0,5) (0,0) 那convex hull是前三个点，这也是唯一的三角形取法 不过它的圆心在 (0,0) 这显然不是最大空圆的圆心 : 其实这也是一个题目，SPOJ34或POJ1379。 : 原本我已实作出O(N^4)的代码，我用假设的方式， : 将convex hull的所有点数当成"新的N"套入这个O(N^4)的算法。 : 再计算矩形4个角，矩形4个边的其中一个边上所有点，矩形中心点， : 总共这麽多的运算，幸运地AC了。 : 关键应该是原本的N至多1000点，跑O(N^4)很慢。 : 但是我把convex hull的总点数来跑O(N^4)就很快了， : 以上提供给需要解题的人。 这题的测资大小，看起来是O(N^2lgN)就够了 方法是枚举每个点p，求p对其它所有点连线段的中垂线的半平面交集 N条直线的半平面交可以O(NlgN)做完，而可能的LEC圆心则必在半平面交的顶点上 (其实这个就是Voronoi了，不过比较好做一点，当然时间复杂度也比较差一点) : : 回到第一篇， : : Voronoi Diagram 的 edge 其实就是两个最近点间的中垂线"段"， : : 在这线段上任何一个位置当做圆心， : : 都可以画出一个圆使得两点落在圆周上，且圆内无其它点。 : : 而 vertice 则是三条 edge 的交点，也就是三点的外心， : : 并且保证圆内也不会有其他点。 : 结果我还是没有实作出O(NlogN)的算法，sigh... 这个超级不好写噢XDD 有兴趣可以看一下这个 http://oistorer.blogspot.com/2006/08/2006_15.html 里面有一篇 《浅析平面Voronoi图的构造及应用》 提到了做法和一些应用 它用的是divide&conquer的方法，对於两个不相交各N/2个点的triangulation 我们有(说来容易的)方法可以在O(N)的时间合并它们 不过要真的写到O(NlogN)的话就.. 有点不太健康 -- +1 ironwood branch --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.30.137 ※ 编辑: seanwu 来自: 140.112.30.137 (12/12 00:17)