ABC 151 F - Enclose All 【Python】
問題はこちら。
import sys
from math import sqrt
readline = sys.stdin.readline
def det(A):
[a, b], [c, d] = A
return a*d - b*c
def solve(A, v):
[a, b], [c, d] = A
z, w = v
x = (d*z - b*w) / det(A)
y = (-c*z + a*w) / det(A)
return x, y
def main():
N = int(readline())
pts = [tuple(map(int, readline().split())) for _ in range(N)]
if N == 2:
(x, y), (z, w) = pts
print(sqrt((x - z)**2 + (y - w)**2) / 2)
return
ans = 10**6
for i1 in range(N):
for i2 in range(i1 + 1, N):
tmp = 0
x1, y1 = pts[i1]
x2, y2 = pts[i2]
x, y = (x1 + x2) / 2, (y1 + y2) / 2
for z, w in pts:
tmp = max(tmp, sqrt((x - z)**2 + (y - w)**2))
ans = min(ans, tmp)
for i1 in range(N):
for i2 in range(i1 + 1, N):
for i3 in range(i2 + 1, N):
tmp = 0
x1, y1 = pts[i1]
x2, y2 = pts[i2]
x3, y3 = pts[i3]
A = [
[x1 - x2, y1 - y2],
[x1 - x3, y1 - y3]
]
v = [
(x1*x1 + y1*y1 - x2*x2 - y2*y2) / 2,
(x1*x1 + y1*y1 - x3*x3 - y3*y3) / 2
]
if det(A) != 0:
x, y = solve(A, v)
else:
x = (min(x1, x2, x3) + max(x1, x2, x3)) / 2
y = (min(y1, y2, y3) + max(y1, y2, y3)) / 2
for z, w in pts:
tmp = max(tmp, sqrt((x - z)**2 + (y - w)**2))
ans = min(ans, tmp)
print(ans)
if __name__ == "__main__":
main()
この記事が気に入ったらサポートをしてみませんか?