主题：求一个算法 -- 东方射日
共:💬55 🌺26
设有四点，ABCD，其中AC两点为最长距离。
BD分别在AC两侧，显然此四点为凸包
且B、D均靠近A，容易保证BD<AC
假设角B和角D均为直角，显然四点均在以AC为直径的圆上。
为简化且不失一般性，设AC水平于X轴，B在AC上方，D在下方。此时将B向上平移DelX至B'，且不影响B'D<AC.
则可以确定此时角AB'C小于直角。则依前算法，我们选定的圆心为三角形AB'C的外心O，此外心O必然AC上方的AC中垂线上，显然OD>OA,即此时点D落在上述外接圆外。
若此时以OD为半径做圆，又仅有点D一点在圆上，显然不是最小圆
本帖一共被 1 帖 引用 (帖内工具实现)
- 相关回复 上下关系8
压缩 3 层
🙂你说的对。不过那也好办 1 温雅颂 字184 2009-01-08 13:40:01
🙂接近了 东方射日 字336 2009-01-08 14:06:58
🙂我觉得没错了，这似乎就应该是最佳答案了。 温雅颂 字86 2009-01-08 18:17:21
🙂算法有错
🙂你说的对，果然有错 温雅颂 字34 2009-01-09 14:23:58
🙂其实我们很接近一个O(N^2)的算法了 东方射日 字924 2009-01-09 18:45:42
🙂追风兄对具体算法能说下 东方射日 字356 2009-01-09 10:22:07
🙂有人算过了 三力思 字167 2009-01-09 11:24:15