最近翔哥上课讲计算几何这个神奇玩意。然后一堆新高一创新班的都特High，然后我们一堆初二的ZZ全程懵逼。

但是刚开始讲的这个东西还是令人耳目一新的。

何为最小覆盖圆，顾名思义，就是覆盖平面内所有点的最小的圆。

原来随机化算法这么强劲？好了我们来看这个算法——随机增量法

一看名字就知道，先要把输入的点打乱，使其随机化。玄学

然后就是从第一个点开始枚举点\(i\)，如果当前的枚举的点在圆内部，就继续不用管(显然的）。否则就以该点为圆心半径为\(0\)开始枚举\(j(1\le j < i)\) 。

如果\(j\)在当前圆的外面就取点\(i\)和点\(j\)的中点为圆心，距离的一半为半径（两点的最小覆盖圆）。以这个圆再枚举\(k(1\le k<j)\)，然后如果点\(k\)在圆外（这和上面的都是一样的）。就以\(i,j,k\)三点在计算最小覆盖圆。

而这个最小覆盖圆就是前\(i\)个点的最小覆盖圆。

然后最大的问题就在于这个已知三点求圆的圆心及半径的过程了。这里给出弱弱的解析几何方法计算几何我不会啊

我们要先知道一个关于圆的公式：

\(x^2+y^2=r^2\)

然后我们设圆心的坐标为\((x_0,y_0)\)然后就可以列一个三元二次方程解出\(x_0,y_0\)的值。

但是具体的解法太过技术性，找到一篇。请仔细参阅。

然后就是坚定不移的相信自己是欧皇然后不被卡精度

但是这个复杂度就是玄学\(O(n)\)（具体证明参考）

板子（就是那个min_cover_circleEnglish level is too low)

inline DB power(DB x){    return x*x;}inline DB dis(node a,node b){    return sqrt(power(a.x-b.x)+power(a.y-b.y));}inline bool in_circle(node a)    return dis(a,O)<=r?1:0;}inline void calc(DB a,DB b,DB c,DB d,DB e,DB f){    O.x=(b*f-d*e)/(b*c-a*d);    O.y=(c*e-a*f)/(b*c-a*d);}inline void min_cover_circle(void){    register int i,j,k;    random_shuffle(a+1,a+n+1);    for (i=1;i<=n;++i)    if (!in_circle(a[i]))    {        O=a[i]; r=0;        for (j=1;j

最后求出的O就是原点，r是半径。

然后我们来看一些板子题：

这题的数据范围很小。尽管我们\(O(n^3)\)大暴力是可以过的，但是对于新的算法还是要练习一下。

&&&&

BZOJ的数据强度比较高，但那个神奇精度问题实在是。。。。。。

样例保留两位，实际上要保留10位，题目也没讲。这是让我们猜数据范围么？

&&

和BZOJ的基本就是重题，但是多亏洛谷才搞懂了数据范围。

莫名弄了一个玄学省选算法。还是挺棒的。