Cod sursa(job #2492249)

Utilizator Natasa_CNatasa Cirstea Natasa_C Data 14 noiembrie 2019 11:11:08
Problema Cele mai apropiate puncte din plan Scor 5
Compilator py Status done
Runda Arhiva educationala Marime 2.04 kb
from operator import itemgetter
import math

f = open("cmap.in", "r")

if f.mode == 'r':
    f1 = f.readlines()
    f.close()

    n = int((f1[0].split())[0])

    x = []
    for i in range(n):
        line = f1[i+1].split()
        x.append([int(line[0]), int(line[1])])

    x.sort(key=itemgetter(0))

    def distanta(n, x):
        if n == 2:
            return math.sqrt(pow(x[0][0] - x[1][0], 2) + pow(x[0][1] - x[1][1], 2))
        elif n == 3:
            vmin = math.sqrt(pow(x[0][0] - x[1][0], 2) +
                             pow(x[0][1] - x[1][1], 2))
            if math.sqrt(pow(x[0][0] - x[2][0], 2) + pow(x[0][1] - x[2][1], 2)) < vmin:
                vmin = math.sqrt(
                    pow(x[0][0] - x[2][0], 2) + pow(x[0][1] - x[2][1], 2))
            if math.sqrt(pow(x[1][0] - x[2][0], 2) + pow(x[1][1] - x[2][1], 2)) < vmin:
                vmin = math.sqrt(
                    pow(x[1][0] - x[2][0], 2) + pow(x[1][1] - x[2][1], 2))
            return vmin
        else:
            middle = n//2

            # divide points in two parts: left and right
            xs, xd = x[:middle+1], x[middle:]

            # calculate minimum distance in the left part and in the right part
            ds = distanta(len(xs), xs)
            dd = distanta(len(xd), xd)

            # calculate the minimum distance in both parts
            d = min(dd, ds)

            # form the band
            band = []
            for i in range(n):
                if x[i][0] >= (x[middle][0] - d) and x[i][0] <= (x[middle][0] + d):
                    band.append(x[i])

            band.sort(key=itemgetter(1))

            # calculate distances between points situated in the band
            for i in range(len(band) - 7):
                for j in range(i+1, i+8):
                    dist = math.sqrt(
                        pow(band[i][0] - band[j][0], 2) + pow(band[i][1] - band[j][1], 2))
                    if dist < d:
                        d = dist
            return d

    p = distanta(n, x)

    fw = open("cmap.out", "w")
    fw.write(str(p))
    fw.close()