Pagini recente » Cod sursa (job #608046) | Cod sursa (job #382088) | Cod sursa (job #2189660) | Cod sursa (job #1883748) | Cod sursa (job #2486378)
def read_input():
points = []
with open("cmap.in", "r") as fin:
n = int(fin.readline())
for _ in range(0, n):
point = [int(x) for x in fin.readline().split()]
points.append(point)
px = sorted(points, key=lambda x: x[0])
py = sorted(px, key=lambda x: x[1])
return px, py
def compute_distance(A, B):
return (A[0] - B[0]) ** 2 + (A[1] - B[1]) ** 2
def base_case(px):
minim = 4 ** 18
if len(px) == 3:
return min(compute_distance(px[0], px[1]), compute_distance(px[0], px[2]),
compute_distance(px[1], px[2]))
elif len(px) == 2:
return compute_distance(px[0], px[1])
return minim
def compute_strip(strip, d):
minim = d
for i in range(0, len(strip) - 6):
for j in range(i + 1, i + 7):
# if abs(strip[i][1] - strip[j][1]) > d:
# break
# else:
dist = compute_distance(strip[i], strip[j])
if dist < minim:
minim = dist
return minim
def closest_two_points(px, py):
if len(px) <= 3:
return base_case(px)
else:
mid = (len(px)) // 2
d_left = closest_two_points(px[:mid], py[:mid])
d_right = closest_two_points(px[mid:], py[mid:])
d = min(d_left, d_right)
# selectez elementele din (M-d,M+d) crescator dupa coordonata y
strip = []
for punct in py:
if abs(punct[0] - px[mid][0]) <= d:
strip.append(punct)
return min(d, compute_strip(strip, d))
def main():
px, py = read_input()
print(px)
print(py)
with open("cmap.out", 'w') as fout:
fout.write(str((round(closest_two_points(px, py) ** (1 / 2), 6))))
if __name__ == "__main__":
main()