Cod sursa(job #2492664)

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

def sort_x(val):
    return val[0]

def sort_y(val):
    return val[1]

def brute(points):
    minim = 9e18
    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
    return 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):
    minim = d

    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 
  
    return 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])
    left_d = closest_points(px, left_py, mid + 1)
    right_d = closest_points(px[mid + 1:], right_py, n - mid)

    d = min(left_d, right_d)
     
    strip = [] 
    for i in range(len(py)):
        if abs(py[i][0] - mid_point[0]) < d:
            strip.append(py[i])
  
    return min(d, minimum(strip, d) ) 

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 = points[0:n]
    py = points[0:n]
    px.sort(key = sort_x)
    py.sort(key = sort_y)
    g.write("{0:.6f}".format(closest_points(px, py, n)))
    #print("{0:.6f}".format(closest_points(px, py, n)))


if __name__ == "__main__":
    main()