Cod sursa(job #2491199)

Utilizator boguklMirzea Bogdan bogukl Data 12 noiembrie 2019 00:10:37
Problema Cele mai apropiate puncte din plan Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.04 kb
from operator import itemgetter

def main():
	with open('cmap.in','r') as file:
		n = int(file.readline())
		puncte = []
		for i in range(n):
			x = file.readline().strip('\n').split(' ')
			puncte.append( (int(x[0]) , int(x[1]) ) )

	x = sorted(puncte,key=itemgetter(0))
	d = distanta_min(x,l=0,r=n-1)
	with open('cmap.out','w') as file:
		file.write(str(d))
	

def distanta(a,b):
	return ( (b[0]-a[0])**2 + (b[1]-a[1])**2 )**0.5

def distanta_min(x,l,r):
	m = (r+l)//2

	if m == l:
		x = distanta(x[l],x[r])	
		return x
	if m == l+1:
		x = min( distanta(x[l],x[m]) , distanta(x[m],x[r]) )
		return x

	
	d1 = distanta_min(x,l=l,r=m) 
	d2 = distanta_min(x,l=m,r=r)
	d = min(d1,d2)

	pct,nr = [],0
	i = m - 1
	while distanta(x[m] , x[i]) <= d:
		pct.append(x[i])
		i -= 1
		nr += 1

	i = m + 1
	while distanta(x[m] , x[i]) <= d:
		pct.append(x[i])
		i += 1
		nr += 1

	ly = sorted(pct,key=itemgetter(1))
	for i in range(0,nr-1):
		for j in range(1,min(nr-i,8)):
			d1 = distanta(ly[i],ly[j])
			if d1 < d:
				d = d1
	return d

if __name__ == '__main__':
	main()