Cod sursa(job #2521039)

Utilizator AvramDanielAvram Daniel AvramDaniel Data 10 ianuarie 2020 12:13:51
Problema Cele mai apropiate puncte din plan Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.41 kb
import math

in_path = "cmap.in"
out_path = "cmap.out"
out_file = open(out_path, 'w')
str = open(in_path).read()
str = str.split('\n')

point = []

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

def bruteforce(st, dre):
    mn = float("inf")
    for i in range(st, dre - 1):
        for j in range(i+1, dre):
            mn = min(mn, dist(point[i], point[j]))

    return mn


def second(val):
    return val[1]

def cmap(st, dre):
   # print(point[st:dre])
    if dre - st <= 3 :
       # print(bruteforce(st, dre))
        return bruteforce(st, dre)
    mid = (st + dre) // 2
    dl = cmap(st, mid)
    dr = cmap(mid, dre)
    d = min(dl, dr)
    strip = []
    for i in range(st,dre):
        if dist(point[i], point[mid]) <=d :
            strip.append(point[i])

    strip.sort(key = second)
    for i in range(len(strip) - 1):
        for j in range(1, len(strip)):
            if i != mid and j != mid :
                if dist(strip[i], strip[j]) < d:
                    d = dist(strip[i], strip[j])
                if strip[j][1] - strip[i][1] >= d:
                    break
    #print(d)
    return d


n = int(str[0])
for i in range(1, len(str)):
    curr = str[i].split()
    curr[0] = int(curr[0])
    curr[1] = int(curr[1])
    point.append(curr)

point.sort()

print(round(cmap(0, len(point)), 6), file=out_file)
out_file.close()