• 题目地址
• 代码
• Prompt

题目地址

https://ac.nowcoder.com/acm/contest/52826/D

代码

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()

Prompt

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