realsdx

closetpaircopy

Sep 16th, 2019
36
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.11 KB | None | 0 0
  1. import math
  2. def last(n):
  3.     return n[1]
  4. def dist(p1,p2):
  5.     return math.sqrt((p1[0]-p2[0])**2+(p1[1]-p2[1])**2)
  6. def stpCls(st,d):
  7.     m=d
  8.     n=len(st)
  9.     st.sort(key=lambda x:x[1])
  10.     for i in range(n):
  11.         for j in range(i+1,n):
  12.             if dist(st[i],st[j])<m and (st[j][1]-st[i][1])<m:
  13.                 m=dist(st[i],st[j])
  14.     return m
  15. def findDist(pt,n):
  16.     m=float("inf")
  17.     for i in range(n):
  18.         for j in range(i+1,n):
  19.             if dist(pt[i],pt[j])<m:
  20.                 m=dist(pt[i],pt[j])
  21.     return m
  22. def closest(pt,n):
  23.     if n<=3:
  24.         return findDist(pt,n)
  25.     mid=n//2
  26.     mp=pt[mid]
  27.     dl=closest(pt[:mid],mid)
  28.     dr=closest(pt[(mid-1):],n-mid)
  29.     d=min(dl,dr)
  30.     strip=[]
  31.     for i in range(n):
  32.         if abs(pt[i][0]-mp[0])<d:
  33.             strip.append(pt[i])
  34.     return min(d,stpCls(strip,d))
  35. if __name__=="__main__":
  36.     #print("Enter Total No. of points")
  37.     n=int(input())
  38.     #print("Enter Points")
  39.     pt=[]
  40.     for i in range(n):
  41.         inp=[int(x) for x in input().split()]
  42.         pt.append(inp)
  43.     pt.sort()
  44.     print(closest(pt,n))
Add Comment
Please, Sign In to add comment