主题：求一个算法 -- 东方射日

同人在上面给了一个链接，介绍了算法

链接出处

其实我们的解法很接近上面所说的Applet’s Algorithm了

1.找凸包: O(nlogn)

2.找最长连线的两点: O(n)

3.凸包上其他点按与上述两点间的夹角排序: O(n)

4.找到最小夹角（必然大于60，否则断言错误）

5.如果夹角大于90，取两点中点--- 结束

6.如果夹角小于90，取外接圆圆心

7.检查是否有在圆外的顶点：O(n)

8.如果没有--- 结束

9.如果有，先后换掉其中一点，另外一点一一取其他顶点回到步骤三重复，取所有可能解答中的最小圆。这里的复杂度为：2*n*n --> O(n^2)

综上，整体复杂度为O(n^2)

这个算法应该没有错了吧，基于两点假设：

1.最小圆上至少有两点

2.最大距离的两点中至少有一点在圆上。

前面我们的算法缺少了步骤7-9，而且假定最大距离两点都在圆上，这个假定是错误的。

所以找凸包和找最大距离两点是有用的，先以O(nlogn)的代价找到两个点，然后以O(n^2)的代价找到圆。

否则我们没有最大距离的两个点只能一一遍历两点重复步骤3到9，那么整体复杂度为O(n^3)