Pagini recente » Cod sursa (job #2408860) | Cod sursa (job #2447925) | Cod sursa (job #560896) | Cod sursa (job #959794) | Cod sursa (job #2483605)
#Citire date
date=open("date.in","r")
n=int(date.readline())
p=[]#Punctele
for i in range(n):
line=date.readline().split()
p.append((int(line[0]),int(line[1])))
#X-sortat dupa x si Y sortat dupa y
x=sorted(p,key=lambda a:a[0])
y=sorted(p,key=lambda a:a[1])
from math import sqrt
def calcul_dist(a,b):
d=abs((a[1]-a[0]))^2+abs((b[1]-b[0]))^2
return sqrt(d)
def dist_min(st,dr):
#Aflarea dist min din st si dr foloseste sortarea dupa
if dr-st+1<2:
print("Un punct sau niciunul")
return 0
if dr-st+1==2:
return calcul_dist(p[st],p[st+1])
if dr-st+1==3:
d1=calcul_dist(p[st],p[st+1])
d2=calcul_dist(p[st],p[st+2])
d3=calcul_dist(p[st+1],p[st+2])
return min(d1,min(d2,d3))
mp=(st+dr)//2
mx=p[mp][0]#Coordonata x a punctului din mijloc
dst=dist_min(st,mp)
ddr=dist_min(mp+1,dr)
#Pt a aflat dist min din banda folosim sortarea dupa y
d=min(dst,ddr)
#Punem elementele in banda, care se afla la distanta d fata de mx
B=[]
for i in range(st,dr+1):
if abs(y[i][0]-mx)<=d:
B.append(y[i])
#Acum verificam daca exista o distanta mai mica in banda
dB=999999999999
for i in range(len(B)-1):
for j in range(i+1,i+8):
if j<len(B):
dB=calcul_dist(B[i],B[j])
dmin=min(d,dB)
return dmin
d=dist_min(0,n-1)
print(d)