最小圆覆盖
首先
没错，我是个蒟蒻。luogu
流程
圆 C;
for(i=1 to n) {if(P[i] 不在 C 内) {C = {P[i], 0};for(j=1 to i-1) {if(P[j] 不在 C 内) {C = {0.5*(P[i]+P[j]), 0.5*dist(P[i], P[j])};for(k=1 to j-1) {if(P[k] 不在 C 内)C = 外接圆(P[i], P[j], P[k]);}}}}
}随机增量
random_shuffle.
打乱顺序，防止毒瘤。
三点共圆
好像这是解析几何的方法。
就是列出方程。
\[ (x1-x)^{2}+(y1-y)^{2}=r^{2} \]
\[ (x2-x)^{2}+(y2-y)^{2}=r^{2} \]
\[ (x3-x)^{2}+(y3-y)^{2}=r^{2} \]
看到这里其实泥们就不用再看可以自己解出来了。
然后等式1-等式2，等式1-等式3列出两个二元一次方程，整理一下是这样的。
\[ (x1-x2)*x+(y1-y2)*y=\frac{x1^2+y1^2-(x2^2+y2^2)}{2} \]
\[ (x1-x3)*x+(y1-y3)*y=\frac{x1^2+y1^2-(x3^2+y3^2)}{2} \]
可以看做
\[ ax+by=c \]
\[ dx+ey=f \]
那么\(x=\frac{b*f-c*e}{b*d-a*e}, y=\frac{d*c-a*f}{b*d-a*e}\)
模板链接
zoj1450
bzoj1226或者bzoj1337
数据比bzoj强的luogu
各个地方不同，不要VC了
模板
#include <bits/stdc++.h>
using namespace std;
const double eps=1e-10;
struct Point {double x,y;};
double dis(Point a,Point b) {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int n;
Point a[100005],o;
double r;
void circum(Point p1,Point p2,Point p3) {double a=2*(p2.x-p1.x),b=2*(p2.y-p1.y),c=p2.x*p2.x+p2.y*p2.y-p1.x*p1.x-p1.y*p1.y,d=2*(p3.x-p1.x),e=2*(p3.y-p1.y),f=p3.x*p3.x+p3.y*p3.y-p1.x*p1.x-p1.y*p1.y; o.x=(b*f-e*c)/(b*d-e*a);o.y=(d*c-a*f)/(b*d-e*a);r=dis(p1,o);
}
int main() {while(scanf("%d",&n)!=EOF&&n) {for(int i=1;i<=n;++i) scanf("%lf%lf",&a[i].x,&a[i].y);random_shuffle(a+1,a+1+n);o=a[1],r=0;for(int i=2;i<=n;++i) {if(dis(o,a[i])>r+eps) {o=a[i],r=0;for(int j=1;j<=i-1;++j) {if(dis(o,a[j])>r+eps) {o.x=(a[i].x+a[j].x)/2;o.y=(a[i].y+a[j].y)/2;r=dis(o,a[j]);for(int k=1;k<=j-1;++k)if(dis(o,a[k])>r+eps)circum(a[i],a[j],a[k]);}}}}printf("%.10lf\n%.10lf %.10lf\n",r,o.x,o.y);}return 0;
}
