Pagini recente » Cod sursa (job #2988796) | Cod sursa (job #2043870) | Cod sursa (job #1162552) | Cod sursa (job #1018332) | Cod sursa (job #2491665)
import math
from heapq import merge
inputFile = open("cmap.in", "r")
n = inputFile.readline().split()
n = int(n[0])
x = []
y = []
for i in range(n):
punct = inputFile.readline().split()
x.append( [int(punct[0]), int(punct[1]) ] )
x.sort()
for i in range(n):
y.append( [ x[i][1], x[i][0] ] )
def distance(punctA, punctB):
dist = math.sqrt( (punctA[0] - punctB[0]) * (punctA[0] - punctB[0]) + (punctA[1] - punctB[1]) * (punctA[1] - punctB[1]) )
return dist
def merge( left, right, mid ):
i = left
j = mid + 1
aux = []
while i <= mid and j <= right:
if x[i][1] < x[j][1]:
aux.append(x[i])
i += 1
else:
aux.append(x[j])
j += 1
while i <= mid:
aux.append(x[i])
i += 1
while j <= right:
aux.append(x[j])
j += 1
for i in range(len(aux)):
x[left + i] = aux[i]
def divide(left, right, x, y):
if left >= right - 1:
return 999999999
else:
if left + 1 == right:
return distance(x[left], x[left+1])
else:
if left + 2 == right:
return min( distance(x[left], x[left+1]), distance(x[left], x[right]), distance(x[left+1], x[right]) )
mid = (right+left) // 2
dr = divide(left, mid, x, y)
dl = divide(mid+1, right, x, y)
best = min(dr, dl)
for i in range(left, right + 1):
for j in range(i-1, left -1, -1):
best = min(best, distance(x[i], x[j]))
return best
outputFile = open("cmap.out", "w+")
outputFile.write( str(divide(0, n-1, x, y)) )