Problem p02805 (python)

Fixed submission:
import random
import math

def make_circle(points):
	# Convert to float and randomize order
	shuffled = [(float(x), float(y)) for (x, y) in points]
	random.shuffle(shuffled)
	
	# Progressively add points to circle or recompute circle
	c = None
	for (i, p) in enumerate(shuffled):
		if c is None or not is_in_circle(c, p):
			c = _make_circle_one_point(shuffled[ : i + 1], p)
	return c


# One boundary point known
def _make_circle_one_point(points, p):
	c = (p[0], p[1], 0.0)
	for (i, q) in enumerate(points):
		if not is_in_circle(c, q):
			if c[2] == 0.0:
				c = make_diameter(p, q)
			else:
				c = _make_circle_two_points(points[ : i + 1], p, q)
	return c


# Two boundary points known
def _make_circle_two_points(points, p, q):
	circ = make_diameter(p, q)
	left  = None
	right = None
	px, py = p
	qx, qy = q
	
	# For each point not in the two-point circle
	for r in points:
		if is_in_circle(circ, r):
			continue
		
		# Form a circumcircle and classify it on left or right side
		cross = _cross_product(px, py, qx, qy, r[0], r[1])
		c = make_circumcircle(p, q, r)
		if c is None:
			continue
		elif cross > 0.0 and (left is None or _cross_product(px, py, qx, qy, c[0], c[1]) > _cross_product(px, py, qx, qy, left[0], left[1])):
			left = c
		elif cross < 0.0 and (right is None or _cross_product(px, py, qx, qy, c[0], c[1]) < _cross_product(px, py, qx, qy, right[0], right[1])):
			right = c
	
	# Select which circle to return
	if left is None and right is None:
		return circ
	elif left is None:
		return right
	elif right is None:
		return left
	else:
		return left if (left[2] <= right[2]) else right


def make_diameter(a, b):
	cx = (a[0] + b[0]) / 2.0
	cy = (a[1] + b[1]) / 2.0
	r0 = math.hypot(cx - a[0], cy - a[1])
	r1 = math.hypot(cx - b[0], cy - b[1])
	return (cx, cy, max(r0, r1))


def make_circumcircle(a, b, c):
	# Mathematical algorithm from Wikipedia: Circumscribed circle
	ox = (min(a[0], b[0], c[0]) + max(a[0], b[0], c[0])) / 2.0
	oy = (min(a[1], b[1], c[1]) + max(a[1], b[1], c[1])) / 2.0
	ax = a[0] - ox;  ay = a[1] - oy
	bx = b[0] - ox;  by = b[1] - oy
	cx = c[0] - ox;  cy = c[1] - oy
	d = (ax * (by - cy) + bx * (cy - ay) + cx * (ay - by)) * 2.0
	if d == 0.0:
		return None
	x = ox + ((ax*ax + ay*ay) * (by - cy) + (bx*bx + by*by) * (cy - ay) + (cx*cx + cy*cy) * (ay - by)) / d
	y = oy + ((ax*ax + ay*ay) * (cx - bx) + (bx*bx + by*by) * (ax - cx) + (cx*cx + cy*cy) * (bx - ax)) / d
	ra = math.hypot(x - a[0], y - a[1])
	rb = math.hypot(x - b[0], y - b[1])
	rc = math.hypot(x - c[0], y - c[1])
	return (x, y, max(ra, rb, rc))


_MULTIPLICATIVE_EPSILON = 1 + 1e-14

def is_in_circle(c, p):
	return c is not None and math.hypot(p[0] - c[0], p[1] - c[1]) <= c[2] * _MULTIPLICATIVE_EPSILON


# Returns twice the signed area of the triangle defined by (x0, y0), (x1, y1), (x2, y2).
def _cross_product(x0, y0, x1, y1, x2, y2):
	return (x1 - x0) * (y2 - y0) - (y1 - y0) * (x2 - x0)
  
n = int(input())
points = [list(map(int, input().split())) for _ in range(n)]
print(make_circle(points)[2])

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

from scipy.spatial import ConvexHull
  
import math
def gaisin(a, b, c, d, e, f):

    aa = a * a
    bb = b * b
    cc = c * c
    dd = d * d
    ee = e * e
    ff = f * f
    if e==a and c==a:
        M = max(b, d, f)
        m = min(b, d, f)
        return (a, (m+M)/2, (M-m)/2)

    py = ((e - a) * (aa + bb - cc - dd) - (c - a) * (aa + bb - ee- ff)) / (2 * (e - a)*(b - d) - 2 * (c - a) * (b - f))

    px = (2 * (b - f) * py - aa - bb + ee + ff) / (2 * (e - a)) if (e == a) else (2 * (b - d) * py - aa - bb + cc + dd) / (2 * (c - a))

    r = math.hypot(px - a, py - b)

    return (px, py, r)
  
def det(xy1, xy2):
  x1, y1 = xy1
  x2, y2 = xy2
  return (x1-x2)**2 + (y1-y2)**2
def is_naka(cen, han, ten):
  return det(cen, ten) <= han**2
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
ll, lll = zip(*A)
if min(ll) == max(ll):
  print((max(lll)-min(lll))/2)
elif min(lll) == max(lll):
  print((max(ll)-min(ll))/2)
else:
  if n==2:
    kyori = det(A[0], A[1])**0.5
    print(kyori/2)
  else:
    A_vertices = ConvexHull(A).vertices
    l = len(A_vertices)
    ans = float("inf")
    for i in range(l-2):
      for j in range(i+1, l-1):
        for k in range(j+1, l):
          t1, t2, t3 = A[A_vertices[i]], A[A_vertices[j]], A[A_vertices[k]]
          t = [t3, t1, t2]
          a1 = det(t1, t2)
          b1 = det(t2, t3)
          c1 = det(t3, t1)
          q = sorted([(a1, t3), (b1, t1), (c1, t2)])
          c1 = q[0][0]
          C = q[0][1]
          b1 = q[1][0]
          B = q[1][1]
          a1 = q[2][0]
          qq = q[2][1]
          if a1 < b1+c1:
            gx, gy, gr = gaisin(t1[0], t1[1], t2[0], t2[1], t3[0], t3[1])
          else:
            gx = (B[0]+C[0])/2
            gy = (B[1]+C[1])/2
            gr = (a1**0.5)/2
          for w in range(l):
            if w!=i and w!=j and w!=k:
              nt = A[A_vertices[w]]
              if not is_naka((gx, gy), gr, nt):
                break
          else:
            print(gr)
            exit()

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

from scipy.spatial import ConvexHull
  
import math
def gaisin(a, b, c, d, e, f):

    aa = a * a
    bb = b * b
    cc = c * c
    dd = d * d
    ee = e * e
    ff = f * f
    if e==a and c==a:
        eee = max(b, d, f)
        fff = min(b, d, f)
        return (a, (eee+fff)/2, (fff-eee)/2)

    py = ((e - a) * (aa + bb - cc - dd) - (c - a) * (aa + bb - ee- ff)) / (2 * (e - a)*(b - d) - 2 * (c - a) * (b - f))

    px = (2 * (b - f) * py - aa - bb + ee + ff) / (2 * (e - a)) if (e == a) else (2 * (b - d) * py - aa - bb + cc + dd) / (2 * (c - a))

    r = math.hypot(px - a, py - b)

    return (px, py, r)
  
def det(xy1, xy2):
  x1, y1 = xy1
  x2, y2 = xy2
  return (x1-x2)**2 + (y1-y2)**2
def is_naka(cen, han, ten):
  return det(cen, ten) <= han**2
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
ll, lll = zip(*A)
if min(ll) == max(ll):
  print((max(lll)-min(lll))/2)
elif min(lll) == max(lll):
  print((max(ll)-min(ll))/2)
else:
  if n==2:
    kyori = det(A[0], A[1])**0.5
    print(kyori/2)
  else:
    A_vertices = ConvexHull(A).vertices
    l = len(A_vertices)
    ans = float("inf")
    for i in range(l-2):
      for j in range(i+1, l-1):
        for k in range(j+1, l):
          t1, t2, t3 = A[A_vertices[i]], A[A_vertices[j]], A[A_vertices[k]]
          t = [t3, t1, t2]
          a1 = det(t1, t2)
          b1 = det(t2, t3)
          c1 = det(t3, t1)
          q = sorted([(a1, t3), (b1, t1), (c1, t2)])
          c1 = q[0][0]
          C = q[0][1]
          b1 = q[1][0]
          B = q[1][1]
          a1 = q[2][0]
          qq = q[2][1]
          if a1 < b1+c1:
            gx, gy, gr = gaisin(t1[0], t1[1], t2[0], t2[1], t3[0], t3[1])
          else:
            gx = (B[0]+C[0])/2
            gy = (B[1]+C[1])/2
            gr = (a1**0.5)/2
          for w in range(l):
            if w!=i and w!=j and w!=k:
              nt = A[A_vertices[w]]
              if not is_naka((gx, gy), gr, nt):
                break
          else:
            print(gr)
            exit()

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

from scipy.spatial import ConvexHull
  
import math
def gaisin(a, b, c, d, e, f):

    aa = a * a
    bb = b * b
    cc = c * c
    dd = d * d
    ee = e * e
    ff = f * f
    if e==a and c==a:
        M = max(b, d, f)
        m = min(b, d, f)
        return (a, (m+M)/2, (M-m)/2)

    py = ((e - a) * (aa + bb - cc - dd) - (c - a) * (aa + bb - ee- ff)) / (2 * (e - a)*(b - d) - 2 * (c - a) * (b - f))

    px = (2 * (b - f) * py - aa - bb + ee + ff) / (2 * (e - a)) if (e == a) else (2 * (b - d) * py - aa - bb + cc + dd) / (2 * (c - a))

    r = math.hypot(px - a, py - b)

    return (px, py, r)
  
def det(xy1, xy2):
  x1, y1 = xy1
  x2, y2 = xy2
  return (x1-x2)**2 + (y1-y2)**2
def is_naka(cen, han, ten):
  return det(cen, ten) <= han**2
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
if n==2:
  kyori = det(A[0], A[1])**0.5
  print(kyori/2)
else:
  A_vertices = ConvexHull(A).vertices
  l = len(A_vertices)
  ans = float("inf")
  for i in range(l-2):
    for j in range(i+1, l-1):
      for k in range(j+1, l):
        t1, t2, t3 = A[A_vertices[i]], A[A_vertices[j]], A[A_vertices[k]]
        t = [t3, t1, t2]
        a1 = det(t1, t2)
        b1 = det(t2, t3)
        c1 = det(t3, t1)
        q = sorted([(a1, t3), (b1, t1), (c1, t2)])
        c1 = q[0][0]
        C = q[0][1]
        b1 = q[1][0]
        B = q[1][1]
        a1 = q[2][0]
        qq = q[2][1]
        if a1 < b1+c1:
          gx, gy, gr = gaisin(t1[0], t1[1], t2[0], t2[1], t3[0], t3[1])
        else:
          gx = (B[0]+C[0])/2
          gy = (B[1]+C[1])/2
          gr = (a1**0.5)/2
        for w in range(l):
          if w!=i and w!=j and w!=k:
            nt = A[A_vertices[w]]
            if not is_naka((gx, gy), gr, nt):
              break
        else:
          print(gr)
          exit()

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

from scipy.spatial import ConvexHull
  
import math
def gaisin(a, b, c, d, e, f):

    aa = a * a
    bb = b * b
    cc = c * c
    dd = d * d
    ee = e * e
    ff = f * f

    py = ((e - a) * (aa + bb - cc - dd) - (c - a) * (aa + bb - ee- ff)) / (2 * (e - a)*(b - d) - 2 * (c - a) * (b - f))

    px = (2 * (b - f) * py - aa - bb + ee + ff) / (2 * (e - a)) if (e == a) else (2 * (b - d) * py - aa - bb + cc + dd) / (2 * (c - a))

    r = math.hypot(px - a, py - b)

    return (px, py, r)
  
def det(xy1, xy2):
  x1, y1 = xy1
  x2, y2 = xy2
  return (x1-x2)**2 + (y1-y2)**2
def is_naka(cen, han, ten):
  return det(cen, ten) <= han**2
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
if n==2:
  kyori = det(A[0], A[1])**0.5
  print(kyori/2)
else:
  A_vertices = ConvexHull(A).vertices
  l = len(A_vertices)
  ans = float("inf")
  for i in range(l-2):
    for j in range(i+1, l-1):
      for k in range(j+1, l):
        t1, t2, t3 = A[A_vertices[i]], A[A_vertices[j]], A[A_vertices[k]]
        t = [t3, t1, t2]
        a1 = det(t1, t2)
        b1 = det(t2, t3)
        c1 = det(t3, t1)
        q = sorted([(a1, t3), (b1, t1), (c1, t2)])
        c1 = q[0][0]
        C = q[0][1]
        b1 = q[1][0]
        B = q[1][1]
        a1 = q[2][0]
        qq = q[2][1]
        if a1 < b1+c1:
          gx, gy, gr = gaisin(t1[0], t1[1], t2[0], t2[1], t3[0], t3[1])
        else:
          gx = (B[0]+C[0])/2
          gy = (B[1]+C[1])/2
          gr = (a1**0.5)/2
        for w in range(l):
          if w!=i and w!=j and w!=k:
            nt = A[A_vertices[w]]
            if not is_naka((gx, gy), gr, nt):
              break
        else:
          print(gr)
          exit()

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

from scipy.spatial import ConvexHull
  
import math
def gaisin(a, b, c, d, e, f):

    aa = a * a
    bb = b * b
    cc = c * c
    dd = d * d
    ee = e * e
    ff = f * f

    py = ((e - a) * (aa + bb - cc - dd) - (c - a) * (aa + bb - ee- ff)) / (2 * (e - a)*(b - d) - 2 * (c - a) * (b - f))

    px = (2 * (b - f) * py - aa - bb + ee + ff) / (2 * (e - a)) if (c == a) else (2 * (b - d) * py - aa - bb + cc + dd) / (2 * (c - a))

    r = math.hypot(px - a, py - b)

    return (px, py, r)
  
def det(xy1, xy2):
  x1, y1 = xy1
  x2, y2 = xy2
  return (x1-x2)**2 + (y1-y2)**2
def is_naka(cen, han, ten):
  return det(cen, ten) <= han**2
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
if n==2:
  kyori = det(A[0], A[1])**0.5
  print(kyori/2)
else:
  A_vertices = ConvexHull(A).vertices
  l = len(A_vertices)
  ans = float("inf")
  for i in range(l-2):
    for j in range(i+1, l-1):
      for k in range(j+1, l):
        t1, t2, t3 = A[A_vertices[i]], A[A_vertices[j]], A[A_vertices[k]]
        t = [t3, t1, t2]
        a1 = det(t1, t2)
        b1 = det(t2, t3)
        c1 = det(t3, t1)
        q = sorted([(a1, t3), (b1, t1), (c1, t2)])
        c1 = q[0][0]
        C = q[0][1]
        b1 = q[1][0]
        B = q[1][1]
        a1 = q[2][0]
        qq = q[2][1]
        if a1 < b1+c1:
          gx, gy, gr = gaisin(t1[0], t1[1], t2[0], t2[1], t3[0], t3[1])
        else:
          gx = (B[0]+C[0])/2
          gy = (B[1]+C[1])/2
          gr = (a1**0.5)/2
        for w in range(l):
          if w!=i and w!=j and w!=k:
            nt = A[A_vertices[w]]
            if not is_naka((gx, gy), gr, nt):
              break
        else:
          print(gr)
          exit()

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

from scipy.spatial import ConvexHull
  
import math
def gaisin(a, b, c, d, e, f):

    aa = a * a
    bb = b * b
    cc = c * c
    dd = d * d
    ee = e * e
    ff = f * f

    py = ((e - a) * (aa + bb - cc - dd) - (c - a) * (aa + bb - ee- ff)) / (2 * (e - a)*(b - d) - 2 * (c - a) * (b - f))

    px = (2 * (b - f) * py - aa - bb + ee + ff) / (2 * (e - a)) if (c == a) else (2 * (b - d) * py - aa - bb + cc + dd) / (2 * (c - a))

    r = math.hypot(px - a, py - b)

    return (px, py, r)
  
def det(xy1, xy2):
  x1, y1 = xy1
  x2, y2 = xy2
  return (x1-x2)**2 + (y1-y2)**2
def is_naka(cen, han, ten):
  return det(cen, ten) <= han**2
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
if n==2:
  kyori = det(A[0], A[1])**0.5
  print(kyori/2)
else:
  A_vertices = ConvexHull(A).vertices
  l = len(A_vertices)
  ans = float("inf")
  for i in range(l-2):
    for j in range(i+1, l-1):
      for k in range(j+1, l):
        t1, t2, t3 = A[A_vertices[i]], A[A_vertices[j]], A[A_vertices[k]]
        t = [t3, t1, t2]
        a = det(t1, t2)
        b = det(t2, t3)
        c = det(t3, t1)
        q = sorted([(a, t3), (b, t1), (c, t2)])
        c = q[0][0]
        C = q[0][1]
        b = q[1][0]
        B = q[1][1]
        a = q[2][0]
        qq = q[2][1]
        if a < b+c:
          gx, gy, gr = gaisin(t1[0], t1[1], t2[0], t2[1], t3[0], t3[1])
        else:
          gx = (B[0]+C[0])/2
          gy = (B[1]+C[1])/2
          gr = (a**0.5)/2
        for w in range(l):
          if w!=i and w!=j and w!=k:
            nt = A[A_vertices[w]]
            if not is_naka((gx, gy), gr, nt):
              break
        else:
          print(gr)
          exit()