Cod sursa(job #2491641)

Utilizator andreibudoiAndrei Budoi andreibudoi Data 12 noiembrie 2019 21:34:38
Problema Cele mai apropiate puncte din plan Scor 10
Compilator py Status done
Runda Arhiva educationala Marime 2.02 kb
import math
from itertools import combinations

file_in = open("cmap.in", "r")
file_out = open("cmap.out", "w")


def dist(p1, p2):
    return (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2

def bruteForce(Px):
    p1=Px[0]
    p2=Px[1]
    distP=dist(p1,p2)
    len_Px=len(Px)
    if len_Px==2:
        return p1, p2, distP

    for x, y in combinations(Px,2):
        z=dist(x,y)
        if z<distP:
            distP=z
            p1,p2=x,y

    return p1, p2, distP

def closestLR(P_x, P_y, distP, bestpair):
    len_Px = len(P_x)
    len_Py = len(P_y)
    mid = len_Px // 2
    midx = P_x[mid][0]
    bestdist=distP

    for i in range(len_Py - 1):
        for j in range(i + 1, min(i + 7, len_Py)):
            p, q = P_y[i], P_y[j]
            dst = dist(p, q)
            if dst < bestdist:
                bestpair = [p, q]
                bestdist = dst
    return bestpair[0], bestpair[1], bestdist


def closestTwo(Px, Py):
    len_Px = len(Px)
    if len_Px<=3:
        return bruteForce(Px)
    mid = len_Px // 2
    Lx = Px[:mid]
    Rx = Px[mid:]

    midx = Px[mid][0]
    Ly = []
    Ry = []
    for point in Py:
        if point[0] < midx:
            Ly.append(point)
        else:
            Ry.append(point)

    l1, l2, distL = closestTwo(Lx, Ly)
    r1, r2, distR = closestTwo(Rx, Ry)

    bestdist=0
    bestpair=[]
    if distL<distR:
        bestdist=distL
        bestpair=[l1,l2]
    else:
        bestdist=distR
        bestpair=[r1,r2]

    p1, p2, distLR = closestLR(Px,Py,bestdist, bestpair)

    if distLR<bestdist:
        return p1,p2, distLR
    else:
        return bestpair[0], bestpair[1], bestdist


points = []
n = int(file_in.readline())
for line in file_in.readlines():
    line = [int(i) for i in line.split()]
    points.append(line)

Px = sorted(points, key=lambda x: x[0])
Py = sorted(points, key=lambda x: (x[1],x[0]))

p1, p2, d = closestTwo(Px, Py)

# print(round(math.sqrt(d),6))
file_out.write("%f\r" % round(math.sqrt(d),6))