Pagini recente » Cod sursa (job #2793574) | Cod sursa (job #1732471) | Cod sursa (job #572285) | Cod sursa (job #2920943) | Cod sursa (job #2488184)
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(left_x,left_y,right_x,right_y,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,Y):
global dist_min
global dist
if len(X) > 3:
m = len(X) // 2
left_x = X[:m+1]
right_x = X[m:]
left_y = []
right_y = []
for point in Y:
if point[0] < X[m][0]:
left_y.append(point)
elif point[0] > X[m][0]:
right_y.append(point)
else:
left_y.append(point)
right_y.append(point)
divide(left_x,left_y)
divide(right_x,right_y)
get_distance(left_x,left_y,right_x,right_y,m)
elif (len(X) == 3):
dist = 0
distance_3(X[0],X[1],X[2])
if dist < dist_min:
dist_min = dist
file = open("cmap.in","r")
text = file.read()
lines = text.split("\n")
fout = open("cmap.out","w")
n = int(lines[0])
points = []
for i in range(n):
x,y = lines[i+1].split()
points.append((int(x),int(y)))
# sort points on x
X = sorted(points, key = itemgetter(0))
# sort points on y
Y = sorted(points, key = itemgetter(1))
dist = 0
dist_min = math.inf
divide(X,Y)
# print("%.6f" % dist_min)
fout.write("%.6f" % dist_min)