Cod sursa(job #2491676)

Utilizator rocky112233malina oanea rocky112233 Data 12 noiembrie 2019 22:16:14
Problema Cele mai apropiate puncte din plan Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.5 kb
import math

inputFile = open("cmap.in", "r")
n = inputFile.readline().split()
n = int(n[0])

x = []
y = []
for i in range(n):
    punct = inputFile.readline().split()
    x.append( [int(punct[0]), int(punct[1]) ] )
    y.append( [int(punct[1]), int(punct[0])] )

x.sort()

for i in range(n):
    y.append( [ x[i][1], x[i][0] ] )

def distance(punctA, punctB):
    dist = math.sqrt( (punctA[0] - punctB[0]) * (punctA[0] - punctB[0]) + (punctA[1] - punctB[1]) * (punctA[1] - punctB[1])  )
    return dist


def divide(left, right, x, y):
    if left >= right - 1:
        return 999999999

    else:
        if left + 1 == right:
            return distance(x[left], x[left+1])
        else:
            if left + 2 == right:
                return min( distance(x[left], x[left+1]), distance(x[left], x[right]), distance(x[left+1], x[right]) )

        mid = (right+left) // 2
        dr = divide(left, mid, x, y)
        dl = divide(mid+1, right, x, y)

        y[left:right+1].sort()

        best = min(dr,dl)
        v = []

        for i in (left, right):
            if abs(y[i][1] - x[mid][0]) <= best:
                v.append(y[i])

        for i in range( len(v) ):
            for j in range(i+1, len(v)):
                best = min(best, distance(v[i], v[j]))
                if j - i >= 8:
                    j = len(v) + 1
                    i = len(v) + 1
                


        

        return best


print( divide(0, n-1, x, y) )
outputFile = open("cmap.out", "w+")
outputFile.write( str(divide(0, n-1, x, y))  )