Pagini recente » Cod sursa (job #2556834) | Cod sursa (job #102230) | Cod sursa (job #429866) | Cod sursa (job #279362) | Cod sursa (job #2491199)
from operator import itemgetter
def main():
with open('cmap.in','r') as file:
n = int(file.readline())
puncte = []
for i in range(n):
x = file.readline().strip('\n').split(' ')
puncte.append( (int(x[0]) , int(x[1]) ) )
x = sorted(puncte,key=itemgetter(0))
d = distanta_min(x,l=0,r=n-1)
with open('cmap.out','w') as file:
file.write(str(d))
def distanta(a,b):
return ( (b[0]-a[0])**2 + (b[1]-a[1])**2 )**0.5
def distanta_min(x,l,r):
m = (r+l)//2
if m == l:
x = distanta(x[l],x[r])
return x
if m == l+1:
x = min( distanta(x[l],x[m]) , distanta(x[m],x[r]) )
return x
d1 = distanta_min(x,l=l,r=m)
d2 = distanta_min(x,l=m,r=r)
d = min(d1,d2)
pct,nr = [],0
i = m - 1
while distanta(x[m] , x[i]) <= d:
pct.append(x[i])
i -= 1
nr += 1
i = m + 1
while distanta(x[m] , x[i]) <= d:
pct.append(x[i])
i += 1
nr += 1
ly = sorted(pct,key=itemgetter(1))
for i in range(0,nr-1):
for j in range(1,min(nr-i,8)):
d1 = distanta(ly[i],ly[j])
if d1 < d:
d = d1
return d
if __name__ == '__main__':
main()