Cod sursa(job #2492702)

Utilizator puiuaPuiu Ana puiua Data 15 noiembrie 2019 09:58:17
Problema Cele mai apropiate puncte din plan Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 2.49 kb
import math

def dist(p1, p2):
    return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)

def closest_split_pair(p_x, p_y, delta, best_pair):
    ln_x = len(p_x)  # store length - quicker
    mx_x = p_x[ln_x // 2][0]  # select midpoint on x-sorted array    # Create a subarray of points not further than delta from
    # midpoint on x-sorted array    
    s_y = [x for x in p_y if mx_x - delta <= x[0] <= mx_x + delta]    
    best = delta  # assign best value to delta
    ln_y = len(s_y)  # store length of subarray for quickness
    for i in range(ln_y - 1):
        for j in range(i+1, min(i + 7, ln_y)):
            p, q = s_y[i], s_y[j]
            dst = dist(p, q)
            if dst < best:
                best_pair = p, q
                best = dst
    return best_pair[0], best_pair[1], best

def brute(points):
    minim = 9e18
    
    for i in range(len(points)):
        for j in range(i + 1, len(points)):
            d = dist(points[i], points[j])
            if d < minim:
                minim = d
                p1, p2 = points[i], points[j] 

    return p1, p2, minim

def closest_pair(ax, ay):
    ln_ax = len(ax)
    if ln_ax <= 3:
        return brute(ax)  
    mid = ln_ax // 2  
    Qx = ax[:mid]  
    Rx = ax[mid:]    
       
    midpoint = ax[mid][0]  
    Qy = list()
    Ry = list()
    for x in ay:  
        if x[0] <= midpoint:
           Qy.append(x)
        else:
           Ry.append(x)        
    (p1, q1, mi1) = closest_pair(Qx, Qy)
    (p2, q2, mi2) = closest_pair(Rx, Ry)    
       
    if mi1 <= mi2:
        d = mi1
        mn = (p1, q1)
    else:
        d = mi2
        mn = (p2, q2)    

    (p3, q3, mi3) = closest_split_pair(ax, ay, d, mn)       

    if d <= mi3:
        return mn[0], mn[1], d
    else:
        return p3, q3, mi3


def main():
    #points = [ (2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
    #points = [(26, 77), (12, 37), (14, 18), (19, 96), (71, 95), (91, 9), (98, 43), (66, 77), (2, 75), (94, 91)]
    f = open("cmap.in", "r")
    g = open("cmap.out", "w")
    n = int(f.readline())
    text = f.read()
    text = [item.split() for item in text.split('\n')[:n+1]]
    points = []

    for i in text:
        points.append((int(i[0]), int(i[1])))

    px = sorted(points, key=lambda x: x[0])  
    py = sorted(points, key=lambda x: x[1])
    p1, p2, mi = closest_pair(px, py)  # Recursive D&C function
    g.write("{0:.6f}".format(mi))

if __name__ == "__main__":
    main()