【计算几何】Python求解覆盖N个点的最小圆

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) 

Given N points, let's draw the smallest circle that contains all the points.

python code

input
6
8.0 9.0
4.0 7.5
1.0 2.0
5.1 8.7
9.0 2.0
4.5 1.0

output
5.0000000000
5.0000000000 5.0000000000