Pagini recente » Cod sursa (job #2973467) | Cod sursa (job #2154426) | Cod sursa (job #2988414) | Cod sursa (job #2267554) | Cod sursa (job #2491916)
fin=open("cmap.in",'r')
n=fin.readline()
n=int(n)
coordinates=[]
for i in range(n):
x,y=fin.readline().split()
x, y = float(x), float(y)
coordinates.append([x,y])
fin.close()
fout=open("cmap.out",'w')
from math import sqrt
def distance(A,B):
return sqrt((A[0]-B[0])**2+(A[1]-B[1])**2)
def bruteForce(P,n):
minim=1000
for i in range(n):
for j in range(i+1,n):
if distance(P[i],P[j])<minim:
minim=distance(P[i],P[j])
return minim
def sortSecond(val):
return val[1]
def strip(D,d):
D.sort(key=sortSecond)
minim=d
for i in range(len(D)):
for j in range(i+1,len(D)):
if D[i][1]-D[j][1]<minim:
if distance(D[i],D[j])<minim:
minim=distance(D[i],D[j])
return minim
def closest(P,n):
if n<=3:
return bruteForce(P,n)
mid=n//2
midPoint=P[mid]
d1=closest(P,mid)
d2=closest([P[x] for x in range(mid,len(P))], n-mid)
d=min(d1,d2)
D=[]
for point in P:
if abs(point[0]-midPoint[0])<d:
D.append(point)
return min(d,strip(D,d))
def sortFirst(val):
return val[0]
coordinates.sort(key=sortFirst)
fout.write(str(closest(coordinates,n)))
fout.close()