Pagini recente » Cod sursa (job #1334530) | Cod sursa (job #1383384) | Cod sursa (job #2355504) | Monitorul de evaluare | Cod sursa (job #2487792)
#Citire date
#date=open("date.in","r")
date=open("cmap.in","r")
out=open("cmap.out","w")
n=int(date.readline())
p=[]#Punctele
for i in range(n):
line=date.readline().split()
p.append((int(line[0]),int(line[1])))
#p.sort()
def merge(st,m,dr,p):
i=st
j=m+1
r=[]
while i<=m and j<=dr:
if(p[i][1]<p[j][1]):
r.append(p[i])
i+=1
else:
r.append(p[j])
j+=1
while i<=m:
r.append(p[i])
i+=1
while j<=dr:
r.append(p[j])
j+=1
for i in range(st,dr+1):
p[i]=r[i-st]
from math import sqrt
def calcul_dist(a,b):
d=(a[1]-b[1])*(a[1]-b[1])+(a[0]-b[0])*(a[0]-b[0])
return sqrt(d)
def dist_min(st,dr,p):
#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
dst=dist_min(st,mp,p)
ddr=dist_min(mp+1,dr,p)
d=min(dst,ddr)
#Se sorteaza partea st si dr dupa ordonata
merge(st,mp,dr,p)
mx=p[mp][0]#Coordonata x a punctului din mijloc
#Punem elementele in banda, care se afla la distanta d fata de mx
B=[]
for i in range(st,dr+1):
if abs(p[i][0]-mx)<=d:
B.append(p[i])
#Pt a aflat dist min din banda folosim sortarea dupa y
#Acum verificam daca exista o distanta mai mica in banda
dBmin=999999999999
for i in range(len(B)):
for j in range(i+1,i+8):
if j<len(B):
dB=calcul_dist(B[i],B[j])
d=min(d,dB)
return d
d=dist_min(0,n-1,p)
out.write(d)