Pagini recente » Cod sursa (job #2743841) | Cod sursa (job #3178718) | Cod sursa (job #2413015) | Cod sursa (job #1777426) | Cod sursa (job #2492249)
from operator import itemgetter
import math
f = open("cmap.in", "r")
if f.mode == 'r':
f1 = f.readlines()
f.close()
n = int((f1[0].split())[0])
x = []
for i in range(n):
line = f1[i+1].split()
x.append([int(line[0]), int(line[1])])
x.sort(key=itemgetter(0))
def distanta(n, x):
if n == 2:
return math.sqrt(pow(x[0][0] - x[1][0], 2) + pow(x[0][1] - x[1][1], 2))
elif n == 3:
vmin = math.sqrt(pow(x[0][0] - x[1][0], 2) +
pow(x[0][1] - x[1][1], 2))
if math.sqrt(pow(x[0][0] - x[2][0], 2) + pow(x[0][1] - x[2][1], 2)) < vmin:
vmin = math.sqrt(
pow(x[0][0] - x[2][0], 2) + pow(x[0][1] - x[2][1], 2))
if math.sqrt(pow(x[1][0] - x[2][0], 2) + pow(x[1][1] - x[2][1], 2)) < vmin:
vmin = math.sqrt(
pow(x[1][0] - x[2][0], 2) + pow(x[1][1] - x[2][1], 2))
return vmin
else:
middle = n//2
# divide points in two parts: left and right
xs, xd = x[:middle+1], x[middle:]
# calculate minimum distance in the left part and in the right part
ds = distanta(len(xs), xs)
dd = distanta(len(xd), xd)
# calculate the minimum distance in both parts
d = min(dd, ds)
# form the band
band = []
for i in range(n):
if x[i][0] >= (x[middle][0] - d) and x[i][0] <= (x[middle][0] + d):
band.append(x[i])
band.sort(key=itemgetter(1))
# calculate distances between points situated in the band
for i in range(len(band) - 7):
for j in range(i+1, i+8):
dist = math.sqrt(
pow(band[i][0] - band[j][0], 2) + pow(band[i][1] - band[j][1], 2))
if dist < d:
d = dist
return d
p = distanta(n, x)
fw = open("cmap.out", "w")
fw.write(str(p))
fw.close()