Problem p02805 (python)

Fixed submission:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1
EPS = sys.float_info.epsilon

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

def min_circle(XY):

    def cross(a, b):
        return a.real * b.imag - a.imag * b.real

    def cnv_img(XY):
        return [x + y*1j for x, y in XY]

    def make_circle(a, b):
        c = (a + b) / 2
        r2 = abs(a-c)**2
        return c, r2

    def make_circle3(a, b, c):
        A = abs(b - c)**2
        B = abs(c - a)**2
        C = abs(a - b)**2
        S = cross(b - a, c - a)
        p = (A * (B + C - A) * a + B * (C + A - B)
             * b + C * (A + B - C) * c) / (4 * S * S)
        r2 = abs(p-a)**2
        return p, r2

    def in_circle(p, c, r2):
        return abs(p-c)**2 <= r2 + EPS


    P = cnv_img(XY)
    random.shuffle(P)
    p1 = P[0]
    p2 = P[1]
    c, r2 = make_circle(p1, p2)

    for i in range(2, len(P)):
        if in_circle(P[i], c, r2):
            continue
        c, r2 = make_circle(P[0], P[i])
        for j in range(1, i):
            if in_circle(P[j], c, r2):
                continue
            c, r2 = make_circle(P[i], P[j])
            for k in range(j):
                if not in_circle(P[k], c, r2):
                    c, r2 = make_circle3(P[i], P[j], P[k])
    return c, r2


@mt
def slv(N, XY):
    _, r2 = min_circle(XY)
    return math.sqrt(r2)


def main():
    N = read_int()
    XY = [read_int_n() for _ in range(N)]
    print(slv(N, XY))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1
EPS = sys.float_info.epsilon

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

def min_circle(XY):

    def cross(a, b):
        return a.real * b.imag - a.imag * b.real

    def cnv_img(XY):
        return [x + y*1j for x, y in XY]

    def make_circle(a, b):
        c = (a + b) / 2
        r2 = abs(p1-c)
        return c, r2

    def make_circle3(a, b, c):
        error_print('make_circle3')
        A = abs(b - c)
        B = abs(c - a)
        C = abs(a - b)
        S = cross(b - a, c - a)
        p = (A * (B + C - A) * a + B * (C + A - B)
             * b + C * (A + B - C) * c) / (4 * S * S)
        r2 = abs(p-a)
        return p, r2

    def in_circle(p, c, r2):
        return abs(p-c) <= r2 + EPS


    P = cnv_img(XY)
    random.shuffle(P)
    p1 = P[0]
    p2 = P[1]
    c, r2 = make_circle(p1, p2)

    for i in range(2, len(P)):
        if in_circle(P[i], c, r2):
            continue
        c, r2 = make_circle(P[0], P[i])
        for j in range(1, i):
            if in_circle(P[j], c, r2):
                continue
            c, r2 = make_circle(P[i], P[j])
            for k in range(j):
                if not in_circle(P[k], c, r2):
                    c, r2 = make_circle3(P[i], P[j], P[k])
    return c, r2


@mt
def slv(N, XY):
    ans = 0
    _, r2 = min_circle(XY)
    return r2


def main():
    N = read_int()
    XY = [read_int_n() for _ in range(N)]
    print(slv(N, XY))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, XY):
    def d(i, j):
        return (XY[i][0] - XY[j][0])**2 + (XY[i][1] - XY[j][1])**2

    def d2(i, x, y):
        return (XY[i][0] -x)**2 + (XY[i][1] - y)**2
    md = 0
    for i in range(N):
        for j in range(i+1, N):
            md = max(md, d(i, j))

    for i in range(N):
        for j in range(N):
            for k in range(N):
                if d(i, j) == d(j, k) and d(j, k) == d(j, i):
                    x = (XY[i][0] + XY[j][0] + XY[k][0]) / 3
                    y = (XY[i][1] + XY[j][1] + XY[k][1]) / 3
                    lc = d2(i, x, y)
                    for l in range(N):
                        if d2(l, x, y) > lc + 10**(-6):
                            break
                    else:
                        md = min(lc)

    return math.sqrt(md) / 2


def main():
    N = read_int()
    XY = [read_int_n() for _ in range(N)]
    print(slv(N, XY))


if __name__ == '__main__':
    main()