Cod sursa(job #2486508)

Utilizator aandreiAndrei Stanimir aandrei Data 2 noiembrie 2019 23:33:01
Problema Cele mai apropiate puncte din plan Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.68 kb
import math
class Point:
    def __init__(self,x_init,y_init):
        self.x = x_init
        self.y = y_init
    def __eq__(self, p2):
        return self.x==p2.x and self.y==p2.y
    def __repr__(self):
        return str(self.x) + " " + str(self.y) 
def dist(p1,p2):
    return float((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y))

f= open("cmap.in","r")
lines=f.readlines();
n= (int(lines[0]))
puncte=[Point(int(line.split()[0]),int(line.split()[1])) for line in lines[1:]]

#print(points);
puncte.sort(key=lambda Point: Point.y)

def strip_closest(banda,delta):
    for i in range(len(banda)):
        for j in range(i+1,len(banda)):
            if(abs(banda[j].x-banda[i].x)<delta):
                break;
            else:
                delta=min(delta,dist(banda[j],banda[i]))
    return delta
def distanta_minima(st,dr):
    #print(puncte[st:dr])
    if(dr-st<=1):
        return 9999999999
    elif(dr-st==2):
        return dist(puncte[st],puncte[st+1])
    elif dr-st==3:
        return min(dist(puncte[st],puncte[st+1]),\
                    dist(puncte[st+2],puncte[st+1]),\
                    dist(puncte[st],puncte[st+2]))
    
    mijloc=(st+dr)//2
    distanta_st=distanta_minima(st,mijloc)
    distanta_dr=distanta_minima(mijloc,dr)
    minim=min(distanta_st,distanta_dr)
    
    #strip
    banda=[]
    mij=puncte[mijloc]
     #print(mijloc)
    for p in puncte:
        if dist(p,mij)<minim:
            banda.append(p)
    return min(minim,strip_closest(banda,minim))
    
#for p in points:
#    print(p)
#print(math.sqrt(distanta_mi    nima(points)))
f= open("cmap.out","w+")
f.write(str(math.sqrt(distanta_minima(0,len(puncte)))))