P2533 [AHOI2012]信号塔 P1742 最小圆覆盖

只会随机增量法

正确性：
显然，这个圆一定是某两个点的外接圆或者某个三角形的外接圆 ，否则就可以变得更小了

时间复杂度 期望是\(O（n）\)
我们先随机生成i个点，求出他们的最小覆盖圆，我们可以认为这个圆是由现在在边界上的那三个点来确定的，也就是说当随机生成的最后一个点不是那三个点时，新生成的点就在圆内，否则在圆外，所以第i个点在前i-1个点的最小覆盖圆外的概率只有3/i
三个点，那么期望就是O（n）咯，但是如果是特殊构造的数据可能卡到\(O（n^3）\)

贴下求三角形外接圆圆心坐标的公式

\[\left\{\begin{array}{l} \left(x_{1}-x_{0}\right)^{2}+\left(y_{1}-y_{0}\right)^{2}=r^{2} (1)\\ \left(x_{2}-x_{0}\right)^{2}+\left(y_{2}-y_{0}\right)^{2}=r^{2} (2)\\ \left(x_{3}-x_{0}\right)^{2}+\left(y_{3}-y_{0}\right)^{2}=r^{2} (3) \end{array}\right. \]

1,2相减,1,3相减可以得到

\[ \begin{array}{l} \left(x_{1}-x_{2}\right) x_{0}+\left(y_{1}-y_{2}\right) y_{0}=\frac{\left(x_{1}^{2}-x_{2}^{2}\right)-\left(y_{2}^{2}-y_{1}^{2}\right)}{2} \\ \left(x_{1}-x_{3}\right) x_{0}+\left(y_{1}-y_{3}\right) y_{0}=\frac{\left(x_{1}^{2}-x_{3}^{2}\right)-\left(y_{3}^{2}-y_{1}^{2}\right)}{2} \end{array} \]

\[\begin{array}{l} a=x_{1}-x_{2} \\ b=y_{1}-y_{2} \\ c=x_{1}-x_{3} \\ d=y_{1}-y_{3} \\ e=\frac{\left(x_{1}^{2}-x_{2}^{2}\right)-\left(y_{2}^{2}-y_{1}^{2}\right)}{2} \\ f=\frac{\left(x_{1}^{2}-x_{3}^{2}\right)-\left(y_{3}^{2}-y_{1}^{2}\right)}{2} \end{array} \]

\[\begin{array}{l} x_{0}=\frac{d e-b f}{b c-a d} \\ y_{0}=\frac{a f-c e}{b c-a d} \end{array} \]

#include
#define rep(i,j,k) for(int i(j);i<=k;++i)
#define drp(i,j,k) for(int i(j);i>=k;--i)
#define repg(x) for(int i(G.head[x]);i;i=G.next[i])
#define bug cout<<"~~~~~~~~~~~~~"<<'\n';
using std::cin;
using std::cout;
typedef long long lxl;
template
inline T  max( T a, T b) {
	return a > b ? a : b;
}
template
inline T  min( T a, T b) {
	return a < b ? a : b;
}
std::mt19937 r(std::chrono::system_clock::now().time_since_epoch().count());
const int N = 1e6 + 79;
struct point {
	double x, y;
	point() {
		x = y = 0.0;
	}

} t[N], O; //?2D?

inline double dis(const point &rr,const point &r) {
	return sqrt( (rr.x - r.x) * (rr.x - r.x) + (rr.y - r.y) * (rr.y - r.y));
}


const double eps = 1e-6;
double R;
inline bool incircle(const point &x) {
	return dis(x, O) - R < eps;
}

inline point calc(point p1,point p2,point p3){
    double a,b,c,d,e,f;
    
    a=p2.y-p1.y;
    b=p3.y-p1.y;
    c=p2.x-p1.x;
    d=p3.x-p1.x;
    f=p3.x*p3.x+p3.y*p3.y-p1.x*p1.x-p1.y*p1.y;
    e=p2.x*p2.x+p2.y*p2.y-p1.x*p1.x-p1.y*p1.y;
    
    point ans;
    ans.x=(a*f-b*e)/(2*a*d-2*b*c);
    ans.y=(d*e-c*f)/(2*a*d-2*b*c);
    R=dis(p1,ans);
    return ans;
}




int n;
int main() {
	std::ios::sync_with_stdio(false);

	cin >> n;
	rep(i, 1, n) {
		cin >> t[i].x >> t[i].y;
	}

	srand(r());
	std::random_shuffle(t + 1, t + n + 1);

	O = t[1];
	rep(i, 1, n) {
		if(incircle(t[i])) continue;
		O = t[i];
		rep(j, 1, i - 1) {
			if(incircle(t[j]))	 continue;
			O.x = (t[i].x + t[j].x) / 2.0;
			O.y = (t[i].y + t[j].y) / 2.0;
			R = dis(t[i], t[j]) / 2.0;

			rep(k, 1, j - 1) {
				if(incircle(t[k])) continue;
				{
					O = calc(t[i], t[j], t[k]);
					R = dis(O, t[i]);
				}

			}
		}
	}
	cout << std::fixed << std::setprecision(10) << R << '\n'<< O.x << ' ' << O.y << ' ' ;
	return 0;
}