给2*n+3个点，任意3点不共线任意四点不共圆，找出三个点确定一个圆，使得n个点在圆外n个点在圆内，

Question

rt。st上看到的，目前还没解决。

Answer 1

已解决，有两个O(n)的算法
1. 任意在包围这n个点的凸多边形上找两个点（然后再找第3个点跟这两个点形成圆），计算其余的点跟着两个点形成的夹角（弦对角），选哪个角度的中位数对应的点。然后这三个点形成的圆满足要求，因为四点不共圆，所以有且仅有这3个点在这个圆上，因为只需要找中位数，所以是O(n)算法。