Cod sursa(job #2490755)

Utilizator E.L.Pnz Just E.L. Data 10 noiembrie 2019 20:38:57
Problema Cele mai apropiate puncte din plan Scor 10
Compilator py Status done
Runda Arhiva educationala Marime 1 kb
import math

fin = open("cmap.in",'r')
fout = open("cmap.out",'w')

class punct(object):
	def __init__(self, x, y):
		self.x = int(x)
		self.y = int(y)
	def __str__(self):
		return str(self.x) + " " + str(self.y) + "\n"

def distanta(a,b):
	return math.sqrt(pow(b.x - a.x,2) + pow(b.y - a.y,2))

def DEI(stanga, dreapta):
	if stanga == dreapta:
		return math.inf
	if stanga == dreapta - 1:
		return distanta(puncte[stanga],puncte[dreapta])
	
	mijl = (stanga + dreapta) // 2
	X = DEI(stanga, mijl)
	Y = DEI(mijl + 1, dreapta)
	minim = min(X, Y)
	aux = []
	for i in range(stanga, dreapta+1):
		if abs(puncte[mijl].x - puncte[i].x) < minim:
			aux.append(puncte[i])
	aux.sort(key=lambda punct: punct.y)
	for i in range(0,len(aux)-1):
		for j in range(i+1,len(aux)):
			minim = min(minim, distanta(aux[i],aux[j]))
	return minim


n = int(fin.readline())
puncte = []

for i in range(0,n):
	IN = fin.readline().split(" ")
	puncte.append(punct(IN[0],IN[1]))

puncte.sort(key=lambda punct: punct.x)

fout.write(str(DEI(0,n-1)))