Cod sursa(job #2491668)

Utilizator Aleks223Alexandru-Vlad Adam Aleks223 Data 12 noiembrie 2019 22:05:27
Problema Cele mai apropiate puncte din plan Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.93 kb
import math


class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __repr__(self):
        return str((self.x, self.y))


def distance(A, B):
    return math.sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y))


def closestPair_brute(arr):
    n = len(arr)

    if n < 2:
        return math.inf

    minDist = distance(arr[0], arr[1])

    for i in range(0, n - 1):
        for j in range(i + 1, n):
            if distance(arr[i], arr[j]) < minDist:
                minDist = distance(arr[i], arr[j])

    return minDist


def closestPair(sortedX, sortedY):
    n = len(sortedX)

    if n <= 3:
        return closestPair_brute(sortedX)

    mid = int(n/2)
    xLeft = sortedX[0:mid]
    xRight = sortedX[mid:n]

    xMid = sortedX[mid].x

    yLeft = []
    yRight = []

    n = len(sortedY)

    for i in range(0, n):
        if sortedY[i].x <= xMid:
            yLeft.append(sortedY[i])
        else:
            yRight.append(sortedY[i])

    distLeft = closestPair(xLeft, yLeft)
    distRight = closestPair(xRight, yRight)

    distMin = min(distLeft, distRight)

    yStrip = []
    for i in range(0, n):
        if abs(xMid - sortedY[i].x) < distMin:
            yStrip.append(sortedY[i])

    closest = distMin

    for i in range(0, len(yStrip)):
        k = i + 1

        while k < len(yStrip) and yStrip[k].y - yStrip[i].y < distMin:
            if distance(yStrip[k], yStrip[i]) < closest:
                closest = distance(yStrip[k], yStrip[i])
            k += 1

    return closest


points = []

with open("cmap.in") as f:
    n = int(f.readline())

    for i in range(0, n):
        x, y = f.readline().strip().split()
        x = int(x)
        y = int(y)

        points.append(Point(x, y))

sortedX = sorted(points, key=lambda k: k.x)
sortedY = sorted(points, key=lambda k: k.y)

print(closestPair(sortedX, sortedY))