随机增量算法
可以去参照下面网站中的论文
https://wenku.baidu.com/view/a836ff44ad02de80d4d84095.html
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<string> using namespace std; int n; double x[1000005],y[1000005]; double l,c,r; int op; void find(int a,int b) { l=(x[a]+x[b])/2.0; r=(y[a]+y[b])/2.0; c=sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]))/2.0; } void mo(int kp,int a,int b) { double q=0,qq; int opa,opb; qq=sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]))/2.0; if(qq>q){q=qq;opa=a;opb=b;} qq=sqrt((x[a]-x[kp])*(x[a]-x[kp])+(y[a]-y[kp])*(y[a]-y[kp]))/2.0; if(qq>q){q=qq;opa=a;opb=kp;} qq=sqrt((x[b]-x[kp])*(x[b]-x[kp])+(y[b]-y[kp])*(y[b]-y[kp]))/2.0; if(qq>q){q=qq;opa=a;opb=kp;} l=(x[opa]+x[opb])/2.0; r=(y[opa]+y[opb])/2.0; c=q; } void ajt(int kp,int a,int b) { double k1,k2,k3,k4,mix1,miy1,mix2,miy2,b1,b2,anx,any; int ia,ib,ic,id; ia=ib=ic=id=0; if(x[kp]-x[a]==0)ia=1; if(x[kp]-x[b]==0)ib=1; if(ia==0)k1=(y[kp]-y[a])/(x[kp]-x[a]); if(ib==0)k2=(y[kp]-y[b])/(x[kp]-x[b]); if(ia==1&&ib==1){mo(kp,a,b);return ;} if(ia==0&&ib==0&&k1==k2){mo(kp,a,b);return ;} if(ia==1)k3=0;else {if(k1==0)ic=1;else k3=-1.0/k1;} if(ib==1)k4=0;else {if(k2==0)id=1;else k4=-1.0/k2;} miy1=(y[kp]+y[a])/2.0;mix1=(x[kp]+x[a])/2.0; miy2=(y[kp]+y[b])/2.0;mix2=(x[kp]+x[b])/2.0; b1=miy1-k3*mix1; b2=miy2-k4*mix2; l=(b2-b1)/(k3-k4); r=k3*l+b1; c=sqrt((l-x[kp])*(l-x[kp])+(r-y[kp])*(r-y[kp])); } bool lcr(int a) { double k; k=sqrt((x[a]-l)*(x[a]-l)+(y[a]-r)*(y[a]-r)); if(k<=c)return true; return false; } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); int i,j,k; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]); find(1,2); for(i=3;i<=n;i++){ if(lcr(i))continue; else{ find(1,i); for(j=2;j<i;j++) if(!lcr(j)){ find(j,i); for(k=1;k<=j-1;k++) if(!lcr(k))ajt(k,j,i); } } } printf("%.2lf %.2lf %.2lf",l,r,c); return 0; }