Cod sursa(job #2491570)

Utilizator boguklMirzea Bogdan bogukl Data 12 noiembrie 2019 19:25:08
Problema Cele mai apropiate puncte din plan Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.07 kb
from operator import itemgetter

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

	x = sorted(puncte,key=itemgetter(0))
	y = sorted(puncte,key=itemgetter(1))
	d = distanta_min(x,y,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 banda_ok(p,m,d):
	if p[0] > m[0]:
		x = p[0] - m[0]
	else:
		x = m[0] - p[0]
	if x < d:
		return True
	return False

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

	if m == l:
		d = distanta(x[l],x[r])
		return d
	if m == l+1:
		d = min( distanta(x[l],x[m]) , distanta(x[m],x[r]) )
		return d
	
	d1 = distanta_min(x,y,l=l,r=m) 
	d2 = distanta_min(x,y,l=m,r=r)
	
	d = min(d1,d2)

	ly = []
	for p in y:
		if banda_ok(p,x[m],d):
			ly.append(p)
	nr = len(ly)

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

	return d

if __name__ == '__main__':
	main()