Pagini recente » Cod sursa (job #2958599) | Cod sursa (job #2630498) | Cod sursa (job #2666071) | Cod sursa (job #2973966) | Cod sursa (job #2492554)
from operator import itemgetter
import math
def get_dist(a, b):
return (a[0] - b[0])*(a[0] - b[0]) + (a[1] - b[1])*(a[1] - b[1])
def distanta(st, dr):
if dr - st <= 3:
d = get_dist(x[st], x[st+1])
for i in range(st, dr):
for j in range(i+1, dr+1):
d_min = get_dist(x[i], x[j])
d = min(d, d_min)
return d
else:
middle = st + (dr - st)//2
# calculate minimum distance in the left part and in the right part
ds = distanta(st, middle)
dd = distanta(middle, dr)
# calculate the minimum distance in both parts
d = min(dd, ds)
# form the band
band = []
for i in range(st, dr+1):
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 = get_dist(x[i], x[j])
d = min(d, dist)
return d
x = []
f = open("cmap.in", "r")
if f.mode == 'r':
f1 = f.readlines()
f.close()
n = int((f1[0].split())[0])
for i in range(n):
line = f1[i+1].split()
x.append([int(line[0]), int(line[1])])
x.sort(key=itemgetter(0))
p = distanta(0, n-1)
fw = open("cmap.out", "w")
fw.write(str(p))
fw.close()