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


この記事が気に入ったらサポートをしてみませんか?