Pagini recente » Cod sursa (job #1013148) | Cod sursa (job #2189151) | Cod sursa (job #1012544) | Cod sursa (job #2675825) | Cod sursa (job #2491676)
import math
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]) ] )
y.append( [int(punct[1]), int(punct[0])] )
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 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)
y[left:right+1].sort()
best = min(dr,dl)
v = []
for i in (left, right):
if abs(y[i][1] - x[mid][0]) <= best:
v.append(y[i])
for i in range( len(v) ):
for j in range(i+1, len(v)):
best = min(best, distance(v[i], v[j]))
if j - i >= 8:
j = len(v) + 1
i = len(v) + 1
return best
print( divide(0, n-1, x, y) )
outputFile = open("cmap.out", "w+")
outputFile.write( str(divide(0, n-1, x, y)) )