POJ 1981 Circle and Points AND L3-021 神坛 (30 分)

转载自:http://www.hankcs.com/program/algorithm/poj-1981-circle-and-points.html
题目链接:Circle and Points

解法1：$O(n^{3})$O(n3)

当 n 不为 1 的时候，枚举两个点恰好在圆上，求的两个端点圆心，再枚举其他点

解法2：$O(n^{2} \ log \ n)$O(n2 log n)

枚举一点 i , 以 i 为圆心做单位圆
枚举一点 j , 以 j 为圆心做单位圆
若圆 i 与圆 j 相交，则相交的那段弧（在 i 上的）对于 i ,j 两点作为圆心是最优的
因为是枚举 j ， 因此我们用极坐标来表示弧，重合最多的就是一定要取到 i 点的最优的情况
别人的博客，写的很详细，确实不错，但是有个地方理解了很久，现在还是有点茫然，这篇博客关于三角函数那里，不太好理解，我加表述
首先理解 $atan2$atan2 的用法，思考之后能发现 $atan2$atan2 的取值范围为 $(-π，π)$(−π，π) 而 $acos$acos 的取值 为正数
最终弧的表示范围为为 $[ atan2 - acos， atan2 + acos]$[atan2−acos，atan2+acos]
这就会出现一个问题，不连续，举个例子
假设我输入的为 ：
3
0 0
-1 -0.2
-1 0.2
对于第一个点来说的两个区间算出为[-3.980，-1.908]和[1.908，3.980]（可以通过运行代码输出中间值得到）
按照这篇博客来说，上面的重合区间数为2，然而实际是三，因为 $-3.980 &lt; -3.14=180^{。}$−3.980<−3.14=180。，然后就发现[-3.980，-1.908]，[1.908，3.980]这两个区间交集不为空，但是那篇博客处理方式没有处理这种情况，估计是因为枚举了每个点，然后某个点是要包含的最左上或者左下之类的点，可能没有上述情况，然后我想不到证明。。。希望有人能理解的时候也叫我一下。。。我邮箱[email protected]，万分感谢

由解法 2 引出另外一个类似的题目

L3-021 神坛 (30 分)

传送门

题意

有 n 个点(3 <= n <= 5000)，求 3 个点组成的三角形的面积最小为多少

很容易想到 $O(n^{3})的解法$O(n3)的解法,但是会有部分数据过不去

$O(n^{2}logn)$O(n2logn) 别人的博客

所以正解是什么呢，如果谁知道的，希望能在评论下面@我，谢了。