Pagini recente » Cod sursa (job #652016) | Cod sursa (job #897668) | Cod sursa (job #1065634) | Cod sursa (job #3157508) | Cod sursa (job #2491570)
from operator import itemgetter
def main():
with open('cmap.in','r') as file:
n = int(file.readline())
puncte = [None]*n
for i in range(n):
x = file.readline().strip('\n').split(' ')
puncte[i] = (int(x[0]) , int(x[1]) )
x = sorted(puncte,key=itemgetter(0))
y = sorted(puncte,key=itemgetter(1))
d = distanta_min(x,y,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 banda_ok(p,m,d):
if p[0] > m[0]:
x = p[0] - m[0]
else:
x = m[0] - p[0]
if x < d:
return True
return False
def distanta_min(x,y,l,r):
m = (r+l)//2
if m == l:
d = distanta(x[l],x[r])
return d
if m == l+1:
d = min( distanta(x[l],x[m]) , distanta(x[m],x[r]) )
return d
d1 = distanta_min(x,y,l=l,r=m)
d2 = distanta_min(x,y,l=m,r=r)
d = min(d1,d2)
ly = []
for p in y:
if banda_ok(p,x[m],d):
ly.append(p)
nr = len(ly)
for i in range(0,nr-1):
for j in range(1,min(nr-i,8)):
d1 = distanta(ly[i],ly[i+j])
if d1 < d:
d = d1
return d
if __name__ == '__main__':
main()