Cod sursa(job #2487732)

Utilizator mihai.badilaBadila Mihai mihai.badila Data 5 noiembrie 2019 18:18:12
Problema Cele mai apropiate puncte din plan Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.44 kb
import math

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

def lessThanFour(pts, l, e):
    d1 = eDist(pts[l], pts[l+1])
    if e - l == 3:
        d2 = eDist(pts[l], pts[l+2])
        d3 = eDist(pts[l+1], pts[l+2])
        return d1 if d1 < d2 and d1 < d3 else d2 if d3 else d3
    else:
        return d1

def stripClosest(strip, minDist):
    mini = minDist
    for i in range(len(strip)):
        j = i+1
        while j<len(strip) and (strip[j][1] - strip[i][1]) < mini:
            stripDist = eDist(strip[j], strip[i])
            mini = stripDist if stripDist < mini else mini
            j+=1

    return mini
            
def pointsClosest(pts, start, end):
    n = end - start
    if n < 4:
        return lessThanFour(pts, start, end)

    mid = int((start + end)/2)
    left = pointsClosest(pts, start, mid)
    right = pointsClosest(pts, mid+1, end)
    minDist = left if left < right else right

    strip = []
    for p in pts:
        if abs(p[0] - pts[mid][0]) < minDist:
            strip.append(p)

    sClose = stripClosest(sorted(strip, key = lambda x: x[1]), minDist)
    return minDist if minDist < sClose else sClose

def driveCode():
    n = int(input())
    points = []
    for i in range(n):
        a, b = [int(a) for a in input().split()]
        points.append((a,b))

    print(pointsClosest(sorted(points, key = lambda x: x[0]),0, len(points)-1))

driveCode()