Cod sursa(job #2488178)

Utilizator Natasa_CNatasa Cirstea Natasa_C Data 6 noiembrie 2019 12:46:00
Problema Cele mai apropiate puncte din plan Scor 5
Compilator py Status done
Runda Arhiva educationala Marime 2.71 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])])

    y = sorted(x, key=itemgetter(1))
    x.sort(key=itemgetter(0))

    def min_punct(ds, dd):
        if ds[0] < dd[0]:
            return ds
        else:
            return dd

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

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

            ys, yd = [], []
            for i in range(n):
                if y[i][0] < x[middle][0]:
                    ys.append(y[i])
                elif y[i][0] > x[middle][0]:
                    yd.append(y[i])
                else:
                    ys.append(y[i])
                    yd.append(y[i])

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

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

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

            # calculate distances between points situated in the band
            band_len = len(band)
            for i in range(band_len - 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[0]:
                        d[0] = dist
                        d[1], d[2] = band[i][0], band[i][1]
                        d[3], d[4] = band[j][0], band[j][1]

            return d

    p = distanta(n, x, y)
    
    fw = open("cmap.out", "w")
    fw.write(str(p[0]))
    fw.close()