Pagini recente » Cod sursa (job #2968737) | Cod sursa (job #913604) | Cod sursa (job #1903597) | Cod sursa (job #3151359) | Cod sursa (job #2483961)
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(points, key=lambda x: x[1])
return px, py
def compute_distance(A, B):
return ((A[0] - B[0]) ** 2 + (A[1] - B[1]) ** 2) ** (1 / 2)
def base_case(px):
minim = 10 ** 18
for i in range(0, len(px) - 1):
for j in range(i + 1, len(px)):
dist = compute_distance(px[i], px[j])
if dist < minim:
minim = dist
poz = [i, j]
return minim
def compute_strip(strip, d):
minim = d
for i in range(0, len(strip) - 1):
for j in range(i + 1, len(strip)):
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 + 1:], py[mid + 1:])
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(closest_two_points(px, py)))
if __name__ == "__main__":
main()