首先我写了个凸包就溜了

这是最小圆覆盖问题，今晚学了一下

先随机化点，一个个加入

假设当前圆心为o，半径为r，加入的点为i

若i不在圆里面，令圆心为i，半径为0

再重新从1~i-1不停找j不在圆里面，令圆心为ij中点，直径为ij距离

再重新在1~j-1不停找k不在圆里面，三点可确定一圆，初中数学

复杂度看似O(n^3)实则O(n)，好玄学

坑点：注意如果用点斜式表示方程有斜率为不存在的情况，需要特判

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const double eps=1e-8;double sqr(double x){ return x*x;}struct point{ double x,y;point(){} point(double X,double Y){x=X,y=Y;} };double getdis(point p1,point p2){ return sqrt(sqr(p1.x-p2.x)+sqr(p1.y-p2.y));}point middle(point p1,point p2){ return point((p1.x+p2.x)/2,(p1.y+p2.y)/2);}double slope (point p1,point p2){ if(p2.x==p1.x)return 0; return (p2.y-p1.y)/(p2.x-p1.x);}double multi(point p1,point p2,point p0){ double x1,y1,x2,y2; x1=p1.x-p0.x; y1=p1.y-p0.y; x2=p2.x-p0.x; y2=p2.y-p0.y; return x1*y2-x2*y1;}struct segment{ double k,b;segment(){} segment(double K,double B){k=K,b=B;} };segment getseg(double k,point pp){ return segment(k,pp.y-k*pp.x);}point intersection(segment s1,segment s2){ double x=(s2.b-s1.b)/(s1.k-s2.k); double y=s1.k*x+s1.b; return point(x,y);}//--------------------------------------simple--------------------------------------------------------int n; point p[1100000];bool cmp(point p1,point p2){ double d=multi(p1,p2,p[1]); if(fabs(d)<=eps)return getdis(p1,p[1])
           
            0;}int top,sta[1100000];void graham(){ sort(p+2,p+n+1,cmp); top=0;sta[++top]=1,sta[++top]=2; double g; for(int i=3;i<=n;i++) { while(top>=2) { g=multi(p[sta[top]],p[i],p[sta[top-1]]); if(g<0||fabs(g)<=eps)top--; else break; } sta[++top]=i; }}//------------------------------------graham----------------------------------------------------------point getcore(point p1,point p2,point p3){ double g=multi(p1,p2,p3); if(fabs(g)<=eps) { double d1=getdis(p1,p2),d2=getdis(p1,p3),d3=getdis(p2,p3); if(d1>d2&&d1>d3)return middle(p1,p2); if(d2>d1&&d2>d3)return middle(p1,p3); if(d3>d1&&d3>d2)return middle(p2,p3); } else { segment s1,s2; if(slope(p1,p2)==0) { s1=getseg(-1/slope(p1,p3),middle(p1,p3)); s2=getseg(-1/slope(p2,p3),middle(p2,p3)); } else if(slope(p1,p3)==0) { s1=getseg(-1/slope(p1,p2),middle(p1,p2)); s2=getseg(-1/slope(p2,p3),middle(p2,p3)); } else { s1=getseg(-1/slope(p1,p2),middle(p1,p2)); s2=getseg(-1/slope(p1,p3),middle(p1,p3)); } return intersection(s1,s2); }}void circlecover(){ random_shuffle(sta+1,sta+top+1); point o=p[sta[1]];double r=0,d; for(int i=2;i<=top;i++) if(getdis(o,p[sta[i]])>r) { o=p[sta[i]],r=0; for(int j=1;j
            
             r) { o=middle(p[sta[i]],p[sta[j]]),r=getdis(o,p[sta[i]]); for(int k=1;k
             
              r) o=getcore(p[sta[i]],p[sta[j]],p[sta[k]]),r=getdis(o,p[sta[i]]); } } printf("%.2lf %.2lf %.2lf\n",o.x,o.y,r);}//------------------------------------solve----------------------------------------------------------int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%lf%lf",&p[i].x,&p[i].y); if(p[i].y