pypy3 解法, 执行用时: 569ms, 内存消耗: 70100K, 提交时间: 2023-04-07 18:56:01

import sys
import math

def euclidean_distance(p1, p2):
    return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)

def make_circle(points):
    shuffled = list(points)
    circle = (0, 0, 0)
    for i, p in enumerate(shuffled):
        if is_inside_circle(circle, p):
            continue
        circle = (p[0], p[1], 0)
        for j, q in enumerate(shuffled[:i]):
            if is_inside_circle(circle, q):
                continue
            circle = ((p[0] + q[0]) / 2, (p[1] + q[1]) / 2, euclidean_distance(p, q) / 2)
            for k, r in enumerate(shuffled[:j]):
                if is_inside_circle(circle, r):
                    continue
                circle = make_circumcircle(p, q, r)
    return circle

def is_inside_circle(circle, point):
    center, radius = (circle[0], circle[1]), circle[2]
    return euclidean_distance(center, point) <= radius

def make_circumcircle(p1, p2, p3):
    d = 2 * (p1[0] * (p2[1] - p3[1]) + p2[0] * (p3[1] - p1[1]) + p3[0] * (p1[1] - p2[1]))
    ux = ((p1[0] ** 2 + p1[1] ** 2) * (p2[1] - p3[1]) + (p2[0] ** 2 + p2[1] ** 2) * (p3[1] - p1[1]) + (p3[0] ** 2 + p3[1] ** 2) * (p1[1] - p2[1])) / d
    uy = ((p1[0] ** 2 + p1[1] ** 2) * (p3[0] - p2[0]) + (p2[0] ** 2 + p2[1] ** 2) * (p1[0] - p3[0]) + (p3[0] ** 2 + p3[1] ** 2) * (p2[0] - p1[0])) / d
    r = euclidean_distance((ux, uy), p1)
    return (ux, uy, r)

def main():
    N = int(input().strip())
    points = [tuple(map(float, input().strip().split())) for _ in range(N)]

    circle = make_circle(points)
    print("{:.10f}".format(circle[2]))
    print("{:.10f} {:.10f}".format(circle[0], circle[1]))

if __name__ == "__main__":
    main()

C++(g++ 7.5.0) 解法, 执行用时: 169ms, 内存消耗: 3536K, 提交时间: 2023-03-15 20:25:40

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
struct node{
	double x,y;
}a[maxn];
double r;
node o;
double dis(node x,node y){
	return sqrt((x.x-y.x)*(x.x-y.x)+(y.y-x.y)*(y.y-x.y));
}
void work(node p1,node p2,node 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;
	o.x=(a*f-b*e)/(2*a*d-2*b*c);
	o.y=(d*e-c*f)/(2*a*d-2*b*c);
	r=dis(o,p1);
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y;
	}
	random_shuffle(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		if(dis(o,a[i])>r){
			o=a[i],r=0;
			for(int j=1;j<=i-1;j++){
				if(dis(o,a[j])>r){
					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){
							work(a[i],a[j],a[k]);
						}
					}
				}
			}
		}
	}
	printf("%.10f\n%.10f %.10f",r,o.x,o.y);
	return 0;
}