C++14(g++5.4) 解法, 执行用时: 275ms, 内存消耗: 8100K, 提交时间: 2020-10-05 19:19:16

#include<bits/stdc++.h>
#define eps 1e-6
using namespace std;

const int maxn=1e6+10;
struct node{
    double x,y;
}p[maxn],o;

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

node circle(node a,node b,node c)//三点共圆圆心公式
{
    double X=( (a.x*a.x-b.x*b.x+a.y*a.y-b.y*b.y)*(a.y-c.y)-(a.x*a.x-c.x*c.x+a.y*a.y-c.y*c.y)*(a.y-b.y) ) / (2*(a.y-c.y)*(a.x-b.x)-2*(a.y-b.y)*(a.x-c.x));
    double Y=( (a.x*a.x-b.x*b.x+a.y*a.y-b.y*b.y)*(a.x-c.x)-(a.x*a.x-c.x*c.x+a.y*a.y-c.y*c.y)*(a.x-b.x) ) / (2*(a.y-b.y)*(a.x-c.x)-2*(a.y-c.y)*(a.x-b.x));
    double R=sqrt((X-a.x)*(X-a.x)+(Y-a.y)*(Y-a.y));
    return (node){X,Y};
}

double r=0;

void minicircle(int n)
{
    o=p[0],r=0;
    for(int i=0;i<n;i++){
        if(dis(p[i],o)-r>eps){
            o=p[i];r=0;
            for(int j=0;j<i;j++){
                if(dis(p[j],o)-r>eps){
                    o={(p[i].x+p[j].x)/2.0,(p[i].y+p[j].y)/2.0};
                    r=dis(p[i],p[j])/2.0;
                    for(int k=0;k<j;k++){
                        if(dis(p[k],o)-r>eps){
                            o=circle(p[i],p[j],p[k]);
                            r=dis(p[i],o);
                        }
                    }
                }
            }
        }
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
    srand((unsigned long)time(NULL));
    random_shuffle(p,p+n);
    minicircle(n);
    printf("%.2f %.2f %.2f\n",o.x,o.y,r);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 257ms, 内存消耗: 8132K, 提交时间: 2020-10-16 20:07:20

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long
#define f(i,a,b) for(int i=a;i<=b;i++)
#define inf 0x7f7f7f7f;
const double eps=1e-5;
struct dot{
    double x,y;
}p[1000010],ans;
ll n;
double ar;
double dis(dot a,dot b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
dot Ce(dot p1,dot p2,dot 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;
    return (dot){(a*f-b*e)/(2*a*d-2*b*c),(d*e-c*f)/(2*a*d-2*b*c)};
}
int main(){
    
    scanf("%lld",&n);
    f(i,1,n)scanf("%lf%lf",&p[i].x,&p[i].y);
    //cout<<Ce(p[1],p[2],p[3]).x;
    //random_shuffle(p+1,p+n+1);
    ar=dis(p[1],p[2])/2.0,ans=(dot){(p[1].x+p[2].x)/2.0,(p[1].y+p[2].y)/2.0};
    f(i,2,n)
        if(dis(p[i],ans)>ar+eps){
            ans=p[i],ar=0;
            f(j,1,i-1)
                if(dis(p[j],ans)>ar+eps){
                    ans=(dot){(p[i].x+p[j].x)/2.0,(p[i].y+p[j].y)/2.0};
                    ar=dis(ans,p[i]);
                    f(k,1,j-1)if(dis(p[k],ans)>ar+eps)ans=Ce(p[i],p[j],p[k]),ar=dis(ans,p[i]);
                }
        }
    printf("%.2lf %.2lf %.2lf",ans.x,ans.y,ar);
    return 0;
}