Problem p02805 (python)

Fixed submission:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True


def check(x,y,r):
    for s,t in c:
        if (x-s)**2+(y-t)**2>r+1e-6:
            return False
    return True
    

def cir3(x1,y1,x2,y2,x3,y3):
    p = ((y1-y3)*(y1**2 -y2**2 +x1**2 -x2**2) -(y1-y2)*(y1**2 -y3**2 +x1**2 -x3**2)) / (2*(y1-y3)*(x1-x2)-2*(y1-y2)*(x1-x3))
    q = ((x1-x3)*(x1**2 -x2**2 +y1**2 -y2**2) -(x1-x2)*(x1**2 -x3**2 +y1**2 -y3**2)) / (2*(x1-x3)*(y1-y2)-2*(x1-x2)*(y1-y3))
    r=((x1-p)**2+(y1-q)**2)
    
    return p,q,r

def rot(x,y,q):
    s=x*math.cos(q)-y*math.sin(q)
    t=x*math.sin(q)+y*math.cos(q)
    return (s,t)
    
    
def cir2(x1,y1,x2,y2):
    p,q=(x1+x2)/2,(y1+y2)/2
    r=((x1-p)**2+(y1-q)**2)
    return p,q,r

ans=inf

n=I()
c=[]
CC=[]
rx=random.randint(1,10**3)
ry=random.randint(1,10**3)
for i in range(n):
    x,y=LI()
    x+=rx
    y+=ry
    CC.append((x,y))


def solve():
    ans=inf
    q=math.pi*random.randint(1,10**4)/10**4
    
    for i in range(n):
        x,y=CC[i]
        x,y=rot(x,y,q)
        c.append((x,y))
    
    
    
    for i in range(n):
        for j in range(i+1,n):
                po=c[i]+c[j]
                x1,y1,x2,y2=po
                p,q,r=cir2(x1,y1,x2,y2)
                
                if check(p,q,r):
                    ans=min(ans,r)
    
    
    for i in range(n):
        for j in range(i+1,n):
            for k in range(j+1,n):
                x1,y1,x2,y2,x3,y3=CC[i]+CC[j]+CC[k]
                a,b= (x2-x1),(y2-y1)
                C,D= (x3-x1),(y3-y1)
                if a*D==b*C:
                    continue
                x1,y1,x2,y2,x3,y3=c[i]+c[j]+c[k]
                p,q,r=cir3(x1,y1,x2,y2,x3,y3)
                
                if check(p,q,r):
                    ans=min(ans,r)

    return ans

an=inf
for rn in range(1):
    an=min(an,solve())
    

print(an**0.5)

Buggy submission (verdict: Runtime Error):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True


def check(x,y,r):
    for s,t in c:
        if (x-s)**2+(y-t)**2>r:
            return False
    return True
    

def cir3(x1,y1,x2,y2,x3,y3):
    p = ((y1-y3)*(y1**2 -y2**2 +x1**2 -x2**2) -(y1-y2)*(y1**2 -y3**2 +x1**2 -x3**2)) / (2*(y1-y3)*(x1-x2)-2*(y1-y2)*(x1-x3))
    q = ((x1-x3)*(x1**2 -x2**2 +y1**2 -y2**2) -(x1-x2)*(x1**2 -x3**2 +y1**2 -y3**2)) / (2*(x1-x3)*(y1-y2)-2*(x1-x2)*(y1-y3))
    r=((x1-p)**2+(y1-q)**2)
    
    return p,q,r

def rot(x,y,q):
    s=x*math.cos(q)-y*math.sin(q)
    t=x*math.sin(q)+y*math.cos(q)
    return (s,t)
    
    
def cir2(x1,y1,x2,y2):
    p,q=(x1+x2)/2,(y1+y2)/2
    r=((x1-p)**2+(y1-q)**2)
    return p,q,r

ans=inf

n=I()
c=[]
CC=[]
for i in range(n):
    x,y=LI()
    CC.append((x,y))





def solve():
    ans=inf
    q=math.pi*random.randint(1,10**4)/10**4
    
    for i in range(n):
        x,y=CC[i]
        x,y=rot(x,y,q)
        c.append((x,y))
    
    
    
    for i in range(n):
        for j in range(i+1,n):
                po=c[i]+c[j]
                x1,y1,x2,y2=po
                p,q,r=cir2(x1,y1,x2,y2)
                
                if check(p,q,r):
                    ans=min(ans,r)
    
    
    for i in range(n):
        for j in range(i+1,n):
            for k in range(j+1,n):
                po=CC[i]+CC[j]+CC[k]
                x1,y1,x2,y2,x3,y3=po
                a,b= (x2-x1),(y2-y1)
                C,D= (x3-x1),(y3-y1)
                if a*D==b*C:
                    0#continue
                po=c[i]+c[j]+c[k]
                x1,y1,x2,y2,x3,y3=po
                p,q,r=cir3(x1,y1,x2,y2,x3,y3)
                
                if check(p,q,r):
                    ans=min(ans,r)
                
                
    return ans

an=inf
for rn in range(1):
    an=min(an,solve())
    

print(an**0.5)

Buggy submission (verdict: Runtime Error):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True


def check(x,y,r):
    for s,t in c:
        if (x-s)**2+(y-t)**2>r**2:
            return False
    return True
    

def cir3(x1,y1,x2,y2,x3,y3):
    p = ((y1-y3)*(y1**2 -y2**2 +x1**2 -x2**2) -(y1-y2)*(y1**2 -y3**2 +x1**2 -x3**2)) / (2*(y1-y3)*(x1-x2)-2*(y1-y2)*(x1-x3))
    q = ((x1-x3)*(x1**2 -x2**2 +y1**2 -y2**2) -(x1-x2)*(x1**2 -x3**2 +y1**2 -y3**2)) / (2*(x1-x3)*(y1-y2)-2*(x1-x2)*(y1-y3))
    r=((x1-p)**2+(y1-q)**2)**0.5
    
    return p,q,r

def rot(x,y,q):
    s=x*math.cos(q)-y*math.sin(q)
    t=x*math.sin(q)+y*math.cos(q)
    return (s,t)
    
    
def cir2(x1,y1,x2,y2):
    p,q=(x1+x2)/2,(y1+y2)/2
    r=((x1-p)**2+(y1-q)**2)**0.5
    return p,q,r

ans=inf

n=I()
c=[]
for i in range(n):
    x,y=LI()
    c.append(rot(x,y,0.001))


for i in range(n):
    for j in range(i+1,n):
            po=c[i]+c[j]
            x1,y1,x2,y2=po
            p,q,r=cir2(x1,y1,x2,y2)
            
            if check(p,q,r):
                ans=min(ans,r)


for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            po=c[i]+c[j]+c[k]
            x1,y1,x2,y2,x3,y3=po
            p,q,r=cir3(x1,y1,x2,y2,x3,y3)
            
            if check(p,q,r):
                ans=min(ans,r)
            
            
print(ans)