Cod sursa(job #2492750)

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

def sort_x(val):
    return val[0]

def sort_y(val):
    return val[1]

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

def distance(a, b):
    return math.sqrt( (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]) )

def minimum(strip, d, p, q):
    minim = d
    p1, p2 = p, q
    for i in range(len(strip)):
        for j in range(i + 1, len(strip)):
            if strip[j][1] - strip[i][1] >= minim:
                break
            else:
                dist = distance(strip[i], strip[j]) 
                if dist < minim:
                    minim = dist 
                    p1, p2 = strip[i], strip[j]
  
    return p1, p2, minim

def closest_points(px, py, n):

    if n <= 3:
        return brute(px) 
    mid = n // 2 
    mid_point = px[mid]
   
    left_py = []
    right_py = []
    
    for i in range(len(py)):
        if py[i][0] <= mid_point[0]:
            left_py.append(py[i])
        else:
            right_py.append(py[i])
    p1, q1, left_d = closest_points(px, left_py, mid + 1)
    p2, q2, right_d = closest_points(px[mid + 1:], right_py, n - mid)

    if left_d < right_d:
        d = left_d
        p = (p1, q1)
    else:
        d = right_d
        p = (p2, q2)
     
    strip = [] 
    for i in range(len(py)):
        if abs(py[i][0] - mid_point[0]) < d:
            strip.append(py[i])
  
    p3, q3, d3 = minimum(strip, d, p[0], p[1])       

    if d <= d3:
        return p[0], p[1], d
    else:
        return p3, q3, d3
 

def main():
    
    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] if item!=""]
    points = []

    for i in text:
        points.append((int(i[0]), int(i[1])))
    
    px = points[0:n]
    py = points[0:n]
    px.sort(key = sort_x)
    py.sort(key = sort_y)

    p, q, d = closest_points(px, py, n)
    g.write("{0:.6f}".format(d))


if __name__ == "__main__":
    main()