Cod sursa(job #2458749)

Utilizator Marius96Marius Gavrilescu Marius96 Data 21 septembrie 2019 13:37:55
Problema Cele mai apropiate puncte din plan Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 0.87 kb
import sys

f = open("cmap.in", 'r')
n = int(f.readline())
a = []
for _ in range(n):
    line = f.readline().split()
    x, y = int(line[0]), int(line[1])
    a.append([x, y])

a = sorted(a, key=lambda x: x[0])
INF = float('inf')

def dist(x, y):
    return (x[0]-y[0])**2 + (x[1]-y[1])**2

def fun(a):
    if len(a) < 2 :
        return INF
    if len(a) == 2:
        return dist(a[0], a[1])
    m = len(a)//2
    s = min(fun(a[:m]), fun(a[m:]))
    mn = INF

    points = [x for x in a if abs(x[0]-a[m][0]) <= s]
    points = sorted(points, key=lambda x: x[1])

    for i in range(len(points)):
        j = i+1
        while j<len(points):
            d = dist(points[j], points[i])
            mn = min(mn, d)
            if points[j][1]-points[i][1] >= s:
                break
            j += 1

    return min(mn, s)

f = open("cmap.out", 'w')
r = fun(a)
f.write(str(r**0.5))