Description：

给出 $N$ 个点，作一个最小的包含所有点的圆。

$1\le n \le 100000$

Solution：

记 $C(A)$ 为点集 $A$ 的最小圆覆盖，那么一定存在点集 $B\subset A$ ， $C(B)=C(A)$ 且 $|B|\le 3$ ，所以，如果 $C(A-\{p\})=C(A)$ ，则 $p\notin B$ ，若 $C(A-\{p\})\ne C(A)$ ，则 $p\in B$ ，所以可以每次随机选三个点作圆，并检查其他所有点是否在这些圆中，如果不在，就把这三个点中的两个和新的点重新画圆，并继续上述过程，可以想到一个 $O(n^4)$ 的做法，就是枚举三个点 $+$ 一重循环判断，但发现可以把判断的一维省略，具体做法是维护一个包含当前的所有点的圆，并不断往这个圆中添加点，如果发现当前枚举的点不在圆中，那么如果是第一层循环枚举的点，那么可以直接和第一个点作圆，如果是第二个点，可以直接和第一个点为直径作圆，如果是第三个点不在圆内，就要作过这三个点的圆，因为 $B$ 中的三个点中一定有两个点在前两重循环中被枚举，所以这样找到的圆一定是包含所有点的圆，由于这个圆不可再缩小，所以是最小圆覆盖， $random\_shuffle$ 一下保证顺序随机，那么每个点都有 $\frac 3 i$ 的几率重构圆，即 $O_1(n)=\sum\frac 3 i O_2(i),O_2{n}=\sum\frac 3 i O_3(i),O_3(n)=n$ 。

所以实际复杂度是 $O(n)$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

struct point

{

	double x,y;

}p[MAXN];

#define eps 1e-8

point operator + (point a,point b){return (point){a.x + b.x,a.y + b.y};}

point operator / (point a,double k){return (point){a.x / k,a.y / k};}

double dis(point a,point b){return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));}

point circle(point a,point b,point c)

{//cout << a.x << " " << a.y << " - " << b.x << " " << b.y << " - " << c.x << " " << c.y << endl;

	double k11,k12,k21,k22,b1,b2;

	if(fabs(a.x - b.x) < eps)//choose a and c,b and c

	{

		k11 = a.x - c.x;k12 = a.y - c.y;b1 = a.x * a.x - c.x * c.x + a.y * a.y - c.y * c.y;

		k21 = b.x - c.x;k22 = b.y - c.y;b2 = b.x * b.x - c.x * c.x + b.y * b.y - c.y * c.y;

	}

	else if(fabs(a.x - c.x) < eps)//choose a and b,b and c

	{

		k11 = a.x - b.x;k12 = a.y - b.y;b1 = a.x * a.x - b.x * b.x + a.y * a.y - b.y * b.y;

		k21 = b.x - c.x;k22 = b.y - c.y;b2 = b.x * b.x - c.x * c.x + b.y * b.y - c.y * c.y;

	}

	else//choose a and b,a and c

	{

		k11 = a.x - b.x;k12 = a.y - b.y;b1 = a.x * a.x - b.x * b.x + a.y * a.y - b.y * b.y;

		k21 = a.x - c.x;k22 = a.y - c.y;b2 = a.x * a.x - c.x * c.x + a.y * a.y - c.y * c.y;

	}

	k11 *= 2;k12 *= 2;k21 *= 2;k22 *= 2;

	//cout << k11 << " " << k12 << " " << b1 << endl;

	//cout << k21 << " " << k22 << " " << b2 << endl;

	double x = (b2 * k12 - b1 * k22) / (k21 * k12 - k11 * k22);

	double y = (b2 * k11 - b1 * k21) / (k22 * k11 - k12 * k21);//cout << x << " " << y << endl;

	return (point){x,y};

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		scanf("%lf%lf",&p[i].x,&p[i].y);

	}

	random_shuffle(p + 1,p + 1 + n);

	point c = p[1];

	double r = 0.0;

	for(int i = 2;i <= n;++i)

	{

		if(dis(c,p[i]) > r + eps)

		{

			c = (p[i] + p[1]) / 2;

			r = dis(p[i],c);

			for(int j = 2;j < i;++j)

			{

				if(dis(c,p[j]) > r + eps)

				{

					c = (p[i] + p[j]) / 2;

					r = dis(c,p[i]);

					for(int k = 1;k < j;++k)

					{

						if(dis(p[k],c) > r + eps)

						{

							c = circle(p[i],p[j],p[k]);

							r = dis(p[i],c);

						}

					}

				}

			}

		}

	}

	printf("%.10lf\n%.10lf %.10lf\n",r,c.x,c.y);

	return 0;

}