Cod sursa(job #2522313)

Utilizator adeenacheAdelina Enache adeenache Data 12 ianuarie 2020 12:33:58
Problema Cele mai apropiate puncte din plan Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 2.02 kb
import math

with open("cmap.in", "r") as f: 
    line = f.readline()
    n = int(line.split(' ')[0])


    points = []
    for i in range(0, n): 
        line = f.readline()
        points.append((int(line.split(' ')[0]), int(line.split(' ')[1])))


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

def smallestDistance(points, left, right): 
    if (right - left + 1 == 2): 
        if points[left][1] > points[right][1]: 
            points[right], points[left] = points[left], points[right]
        return distance(points[right], points[left])
    
    if (right - left + 1 == 3):
        points[left: right + 1] = sorted(points[left: right + 1], key=lambda x: x[1])
        return min(
            distance(points[right], points[left]), 
            distance(points[left + 1], points[left]),
            distance(points[right], points[left + 1])
        )

    mid = (left + right) // 2


    midx = points[mid][0]

    dist = min(smallestDistance(points, left, mid), smallestDistance(points, mid + 1, right))

    # interclasarea punctelor
    i = left
    j = mid + 1
    aux = []

    while i <= mid and j <= right: 
        if (points[i][1] < points[j][1]): 
            aux.append(points[i])
            i += 1
        else: 
            aux.append(points[j])
            j += 1

    while (i <= mid): 
        aux.append(points[i])
        i += 1
    
    while j <= right: 
        aux.append(points[j])
        j += 1
    

    deltaRect = []

    for i in range(left, right + 1): 
        points[i] = aux[i - left]

        if (points[i][0] - midx <= dist and points[i][0] - midx >= -dist): 
            deltaRect.append(points[i])
    

    for i, point in enumerate(deltaRect): 
        for j in range(i + 1, min(len(deltaRect), i + 8)): 
            if (distance(point, deltaRect[j]) < dist): 
                dist = distance(point, deltaRect[j])
    
    return dist


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


with open("cmap.out", "w") as g: 
    g.write("{}".format(dist))