Cod sursa(job #2491665)

Utilizator rocky112233malina oanea rocky112233 Data 12 noiembrie 2019 22:04:44
Problema Cele mai apropiate puncte din plan Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.61 kb
import math
from heapq import merge

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]) ] )

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 merge( left, right, mid ):
    i = left
    j = mid + 1

    aux = []

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

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

    for i in range(len(aux)):
        x[left + i] = aux[i]

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)

        best = min(dr, dl)

        for i in range(left, right + 1):
            for j in range(i-1, left -1, -1):
                best = min(best, distance(x[i], x[j]))

        return best


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