Pagini recente » Cod sursa (job #1081653) | Cod sursa (job #2536074) | Cod sursa (job #2442600) | Cod sursa (job #2708824) | Cod sursa (job #2491764)
from operator import itemgetter
import math
def distance_2(point1, point2):
global dist
dist = math.sqrt((point1[0] - point2[0]) * (point1[0] - point2[0]) + (point1[1] - point2[1]) * (point1[1] - point2[1]))
def distance_3(point1, point2,point3):
global dist
dist_1_2 = math.sqrt((point1[0] - point2[0]) * (point1[0] - point2[0]) + (point1[1] - point2[1]) * (point1[1] - point2[1]))
dist_1_3 = math.sqrt((point1[0] - point3[0]) * (point1[0] - point3[0]) + (point1[1] - point3[1]) * (point1[1] - point3[1]))
dist_2_3 = math.sqrt((point2[0] - point3[0]) * (point2[0] - point3[0]) + (point2[1] - point3[1]) * (point2[1] - point3[1]))
dist = min(dist_1_2,dist_1_3,dist_2_3)
def get_distance(m):
global dist_min
global dist
band = []
for point in Y:
if point[0] > X[m][0] - dist_min and point[0] < X[m][0] + dist_min:
band.append(point)
for i in range(len(band) - 7):
for j in range(1,8):
dist = 0
distance_2(band[i],band[i+j])
if dist < dist_min:
dist_min = dist
def divide(X):
global dist_min
global dist
if len(X) > 3:
m = len(X) // 2
left_x = X[:m+1]
right_x = X[m:]
divide(left_x)
divide(right_x)
get_distance(m)
elif (len(X) == 3):
dist = 0
distance_3(X[0],X[1],X[2])
if dist < dist_min:
dist_min = dist
elif (len(X) == 2):
dist = 0
distance_2(X[0],X[1])
if dist < dist_min:
dist_min = dist
fin = open("cmap.in","r")
text = fin.read()
lines = text.split("\n")
fin.close()
n = int(lines[0])
X = []
for i in range(n):
x,y = lines[i+1].split()
X.append((int(x),int(y)))
# sort points on x
X = sorted(X, key = itemgetter(0))
# sort points on y
Y = sorted(X, key = itemgetter(1))
dist = 0
dist_min = math.inf
divide(X)
fout = open("cmap.out","w")
fout.write("%.6f" % dist_min)
fout.close()