Pagini recente » Cod sursa (job #2517696) | Cod sursa (job #1991886) | Cod sursa (job #2268023) | Cod sursa (job #2490120) | Cod sursa (job #2490755)
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)))