※ 引述《seanwu (海恩)》之铭言： : 呃不知道我有没有误会你的意思... 那例如底下的测资，4个点: : (-4,-3) (4,-3) (0,5) (0,0) : 那convex hull是前三个点，这也是唯一的三角形取法 : 不过它的圆心在 (0,0) 这显然不是最大空圆的圆心 结论应该是：只用convex hull来计算LEC的圆心是错的。 我发现程式跑上述资料因为利用三角形三顶点求出的(0,0) 恰与测资点(0, 0)重合，就被剔除掉了。 所以这个阶段跑不出结果。 但後续的动作跑出的结果弥补了这个缺失， 所以答案会和judge系统上的一样。 附带一提，SPOJ34这题是寻找矩形上或矩形内离测资点为最远距离的点， 就变成即使求出了LEC的圆心，还是要考虑矩形上的可能。 我的程式也做了後半段，才造成幸运的结果。 但是如果只是求LEC的圆心，就不能只用convex hull的方式去做。 : : 其实这也是一个题目，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了，不过比较好做一点，当然时间复杂度也比较差一点) 我有找到利用C++的deque做半平面交的文章， 题目也类似於POJ2451(不过这题是求面积)， 但是对於大前题我就有点疑问了， 疑问就是如何知道中垂线所分成的的半平面是 >= 0 还是 <= 0 如果在不确定的情况下可以直接计算吗？(还没开始动手) 因为POJ2451这题所给的线段已经确定全部都是 >= 0 了。 : : 结果我还是没有实作出O(NlogN)的算法，sigh... : 这个超级不好写噢XDD : 有兴趣可以看一下这个 : http://oistorer.blogspot.com/2006/08/2006_15.html : 里面有一篇 《浅析平面Voronoi图的构造及应用》 : 提到了做法和一些应用 : 它用的是divide&conquer的方法，对於两个不相交各N/2个点的triangulation : 我们有(说来容易的)方法可以在O(N)的时间合并它们 : 不过要真的写到O(NlogN)的话就.. 有点不太健康 嗯，我有空请简体书店订这本， 不过很怕以我的水准会看不懂。 Bleed --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 114.43.124.23