Nu exista pagina, dar poti sa o creezi ...
Cod sursa(job #2486514)
Utilizator | Data | 3 noiembrie 2019 00:13:03 | |
---|---|---|---|
Problema | Cele mai apropiate puncte din plan | Scor | 10 |
Compilator | py | Status | done |
Runda | Arhiva educationala | Marime | 1.82 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")
puncte=f.readlines();
n= (int(puncte[0]))
puncte=[Point(int(line.split()[0]),int(line.split()[1])) for line in puncte[1:]]
#print(points);
puncte.sort(key=lambda Point: Point.x)
#banda=[]
def strip_closest(banda,delta):
banda.sort(key=lambda Point: Point.y)
for i in range(len(banda)):
for j in range(i+1,len(banda)):
if(abs(banda[j].y-banda[i].y)<delta):
break;
else:
delta=min(delta,dist(banda[j],banda[i]))
return delta
def distanta_minima(st,dr):
#print(puncte[st:dr])
#print(puncte[st])
#print(puncte[st+1])
#print(puncte[st+2])
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
minim=min(distanta_minima(st,mijloc),distanta_minima(mijloc,dr))
#strip
banda=[]
mij=puncte[mijloc]
#print(mijloc)
for p in puncte[st:dr]:
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+")
#print(str(math.sqrt(distanta_minima(0,len(puncte)))))
f.write(str(math.sqrt(distanta_minima(0,len(puncte)))))