Problem p02805 (python)

Fixed submission:
import math

def all_points(x, y):
	return max(one_point(x, y, _x, _y) for _x, _y in points)

def one_point(x0, y0, x1, y1):
	return math.pow(x0-x1, 2) + math.pow(y0-y1, 2)

def two():
	for i in range(N):
		for j in range(i+1, N):
			yield (points[i], points[j])

def three():
	for i in range(N):
		for j in range(i+1, N):
			for k in range(j+1, N):
				yield (points[i], points[j], points[k])

def process_two():
	minimum = 1e18
	for (a, b), (c, d) in two():
		x, y = (a+c)/2, (b+d)/2
		minimum = min(minimum, all_points(x, y))
	return minimum

def process_three():
	minimum = 1e18
	for (a,b), (c,d), (e,f) in three():
		try:
			if b==d==f:
				continue
			if d==b:
				a, b, c, d, e, f = e, f, a, b, c, d
			if f==b:
				a, b, c, d, e, f = c, d, e, f, a, b
			m0x, m0y = (a+c)/2, (b+d)/2
			m0 = -(c-a)/(d-b)
			b0 = m0y - m0*m0x
			
			m1x, m1y = (a+e)/2, (b+f)/2
			m1 = -(e-a)/(f-b)
			b1 = m1y - m1*m1x

			x = (b1-b0) / (m0-m1)
			y = m0*x + b0

			minimum = min(minimum, all_points(x, y))
		except ZeroDivisionError:
			continue
	return minimum


N = int(input())
points = []
for i in range(N):
	x, y = map(int, input().split())
	points.append((x, y))


print(math.sqrt(min(process_two(), process_three())))

Buggy submission (verdict: Runtime Error):
import sys
#sys.stdin = open('inp.txt')

def dist(x1, y1, x2, y2):
    return (x1-x2)**2 + (y1-y2)**2

def intersection_points(x1, y1, r1, x2, y2, r2):
    d1 = dist(x1, y1, x2, y2)
    rad = (r1 + r2)**2

    if d1>rad:
        return None
    elif d1==rad:
        x0 = (r1*x2 + r2*x1)/(r1 + r2)
        y0 = (r1*y2 + r2*y1)/(r1 + r2)

        return [(x0, y0)]

    else:
        det_sq = 2*(r1**2 + r2**2)/d1 - (r1**2 - r2**2)**2 / d1**2 - 1
        if det_sq < 0 :
            return None
        det = pow(det_sq, 0.5)/2

        mul = (r1**2 - r2**2)/(2*d1)
        a1 = (x1+x2)/2
        b1 = (y1+y2)/2

        a2 = mul * (x2 - x1)
        b2 = mul * (y2 - y1)

        m1 = a1 + a2 + det * (y2 - y1)
        n1 = b1 + b2 + det * (x1 - x2)

        m2 = a1 + a2 - det * (y2 - y1)
        n2 = b1 + b2 - det * (x1 - x2)

        return [(m1, n1), (m2, n2)]

def check_at_one_inter(P, R):
    L = len(points)
    for i in range(L-1):
        for j in range(i+1, L):
            li = intersection_points(*P[i], R, *P[j], R)
            if li==None:
                continue

            for int_p in li:
                skip = False
                for gen_p in points:
                    d = dist(*int_p, *gen_p)
                    if pow(d, 0.5) - R > 10**(-6):
                        skip  = True
                        break

                if not skip:
                    return True
    return False

def solve(points):
    len_p = len(points)
    m = float('-inf')
    l = len(points)
    for i in range(l-1):
        for j in range(i+1, l):
            m = max(m , pow(dist(*points[i], *points[j]), 0.5))
    
    max_r = int(2*m * 10**8) + 1
    min_r = 1
    #print(m, max_r, min_r)
    ans = float('inf')
    while min_r < max_r:
        mid = (min_r + max_r) //2
        #print('mid', mid)
        ## check mid as R
        R = mid/10**8
        if check_at_one_inter(points, R):
            #print('if')
            ans = min(ans, R)
            max_r = mid
        else:
            #print('else')
            min_r = mid +1

    print('%.6f'%ans)
        
            
points = []
for case in range(int(input())):
    x, y = map(int, input().split())
    points.append((x, y))
    
solve(points)

Buggy submission (verdict: Runtime Error):
import sys
#sys.stdin = open('inp.txt')

def dist(x1, y1, x2, y2):
    return (x1-x2)**2 + (y1-y2)**2

def intersection_points(x1, y1, r1, x2, y2, r2):
    d1 = dist(x1, y1, x2, y2)
    rad = (r1 + r2)**2

    if d1>rad:
        return None
    elif d1==rad:
        x0 = (r1*x2 + r2*x1)/(r1 + r2)
        y0 = (r1*y2 + r2*y1)/(r1 + r2)

        return [(x0, y0)]

    else:
        det_sq = 2*(r1**2 + r2**2)/d1 - (r1**2 - r2**2)**2 / d1**2 - 1
        det = pow(det_sq, 0.5)/2

        mul = (r1**2 - r2**2)/(2*d1)
        a1 = (x1+x2)/2
        b1 = (y1+y2)/2

        a2 = mul * (x2 - x1)
        b2 = mul * (y2 - y1)

        m1 = a1 + a2 + det * (y2 - y1)
        n1 = b1 + b2 + det * (x1 - x2)

        m2 = a1 + a2 - det * (y2 - y1)
        n2 = b1 + b2 - det * (x1 - x2)

        return [(m1, n1), (m2, n2)]

def check_at_one_inter(P, R):
    L = len(points)
    for i in range(L-1):
        for j in range(i+1, L):
            li = intersection_points(*P[i], R, *P[j], R)
            if li==None:
                continue

            for int_p in li:
                skip = False
                for gen_p in points:
                    d = dist(*int_p, *gen_p)
                    if pow(d, 0.5) - R > 10**(-6):
                        skip  = True
                        break

                if not skip:
                    return True
    return False

def solve(points):
    len_p = len(points)
    m = float('-inf')
    l = len(points)
    for i in range(l-1):
        for j in range(i+1, l):
            m = max(m , pow(dist(*points[i], *points[j]), 0.5))
    
    max_r = int(2*m * 10**8) + 1
    min_r = 1
    #print(m, max_r, min_r)
    ans = float('inf')
    while min_r < max_r:
        mid = (min_r + max_r) //2
        #print('mid', mid)
        ## check mid as R
        R = mid/10**8
        if check_at_one_inter(points, R):
            #print('if')
            ans = min(ans, R)
            max_r = mid
        else:
            #print('else')
            min_r = mid +1

    print('%.6f'%ans)
        
            
points = []
for case in range(int(input())):
    x, y = map(int, input().split())
    points.append((x, y))
    
solve(points)

Buggy submission (verdict: Runtime Error):


def dist(x1, y1, x2, y2):
    return (x1-x2)**2 + (y1-y2)**2

def intersection_points(x1, y1, r1, x2, y2, r2):
    d1 = dist(x1, y1, x2, y2)
    rad = (r1 + r2)**2

    if d1>rad:
        return None
    elif d1==rad:
        x0 = (r1*x2 + r2*x1)/(r1 + r2)
        y0 = (r1*y2 + r2*y1)/(r1 + r2)

        return [(x0, y0)]

    else:
        det_sq = 2*(r1**2 + r2**2)/d1 - (r1**2 - r2**2)**2 / d1**2 - 1
        det = pow(det_sq, 0.5)/2

        mul = (r1**2 - r2**2)/(2*d1)
        a1 = (x1+x2)/2
        b1 = (y1+y2)/2

        a2 = mul * (x2 - x1)
        b2 = mul * (y2 - y1)

        m1 = a1 + a2 + det * (y2 - y1)
        n1 = b1 + b2 + det * (x1 - x2)

        m2 = a1 + a2 - det * (y2 - y1)
        n2 = b1 + b2 - det * (x1 - x2)

        return [(m1, n1), (m2, n2)]

def check_at_one_inter(P, R):
    L = len(points)
    for i in range(L-1):
        for j in range(i+1, L):
            li = intersection_points(*P[i], R, *P[j], R)
            if li==None:
                continue

            for int_p in li:
                skip = False
                for gen_p in points:
                    d = dist(*int_p, *gen_p)
                    if pow(d, 0.5) - R > 10**(-6):
                        skip  = True
                        break

                if not skip:
                    return True
    return False

def solve(points):
    len_p = len(points)
    m = float('-inf')
    l = len(points)
    for i in range(l-1):
        for j in range(i+1, l):
            m = max(m , pow(dist(*points[i], *points[j]), 0.5))
    
    max_r = int(2*m * 10**30) + 1
    min_r = 1
    #print(m, max_r, min_r)
    ans = float('inf')
    while min_r < max_r:
        mid = (min_r + max_r) //2
        #print('mid', mid)
        ## check mid as R
        R = mid/10**30
        if check_at_one_inter(points, R):
            #print('if')
            ans = min(ans, R)
            max_r = mid
        else:
            #print('else')
            min_r = mid +1

    print('%.6f'%ans)
        
            
points = []
for case in range(int(input())):
    x, y = map(int, input().split())
    points.append((x, y))
    
solve(points)

Buggy submission (verdict: Runtime Error):
## atcoder problem 6 ever
import sys
#sys.stdin = open('inp.txt')

def dist(x1, y1, x2, y2):
    return (x1-x2)**2 + (y1-y2)**2

def intersection_points(x1, y1, r1, x2, y2, r2):
    d1 = dist(x1, y1, x2, y2)
    rad = (r1 + r2)**2

    if d1>rad:
        return None
    elif d1==rad:
        x0 = (r1*x2 + r2*x1)/(r1 + r2)
        y0 = (r1*y2 + r2*y1)/(r1 + r2)

        return [(x0, y0)]

    else:
        det_sq = 2*(r1**2 + r2**2)/d1 - (r1**2 - r2**2)**2 / d1**2 - 1
        if det_sq < 0:
            print(det_sq)
            print(x1, y1, r1, x2, y2, r2)
            print('bye')
            sys.exit(0)
        det = pow(det_sq, 0.5)/2

        mul = (r1**2 - r2**2)/(2*d1)
        a1 = (x1+x2)/2
        b1 = (y1+y2)/2

        a2 = mul * (x2 - x1)
        b2 = mul * (y2 - y1)

        m1 = a1 + a2 + det * (y2 - y1)
        n1 = b1 + b2 + det * (x1 - x2)

        m2 = a1 + a2 - det * (y2 - y1)
        n2 = b1 + b2 - det * (x1 - x2)

        return [(m1, n1), (m2, n2)]

def check_at_one_inter(P, R):
    L = len(points)
    for i in range(L-1):
        for j in range(i+1, L):
            li = intersection_points(*P[i], R, *P[j], R)
            if li==None:
                continue

            for int_p in li:
                skip = False
                for gen_p in points:
                    d = dist(*int_p, *gen_p)
                    if pow(d, 0.5) - R > 10**(-6):
                        skip  = True
                        break

                if not skip:
                    return True
    return False

def solve(points):
    len_p = len(points)
    m = float('-inf')
    l = len(points)
    for i in range(l-1):
        for j in range(i+1, l):
            m = max(m , pow(dist(*points[i], *points[j]), 0.5))
    
    max_r = int(2*m * 10**30) + 1
    min_r = 1
    #print(m, max_r, min_r)
    ans = float('inf')
    while min_r < max_r:
        mid = (min_r + max_r) //2
        #print('mid', mid)
        ## check mid as R
        R = mid/10**30
        if check_at_one_inter(points, R):
            #print('if')
            ans = min(ans, R)
            max_r = mid
        else:
            #print('else')
            min_r = mid +1

    print('%.6f'%ans)
        
            
points = []
for case in range(int(input())):
    x, y = map(int, input().split())
    points.append((x, y))
    
solve(points)