SHARE
TWEET

v7.1

a guest Aug 21st, 2019 86 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import sys
  2. import math
  3. from datetime import datetime
  4.  
  5. def distX(a, b):
  6.   return a[0] - b[0]
  7.  
  8. def distY(a, b):
  9.   return a[1] - b[1]
  10.  
  11. def dist(a, b):
  12.   return distX(a, b) ** 2  + distY(a, b) ** 2
  13.  
  14. def min(a, b):
  15.   if (a < b):
  16.     return a
  17.   return b
  18.  
  19.  
  20. def bruteForce(points):
  21.   smallest_dist = 1000000000000
  22.   for i in range(len(points)):
  23.     for j in range((i + 1),len(points)):
  24.       current_distance = dist(points[i], points[j])
  25.       if(smallest_dist > 0 and smallest_dist > current_distance ):
  26.         smallest_dist = current_distance
  27.   return smallest_dist
  28.  
  29. def splitPoints(sortedByX, sortedByY, current_smallest_distance, depth):
  30.   # print("new depth ", depth)
  31.   point_count = len(sortedByX)
  32.   middle_index = point_count // 2 #L
  33.   middle_point = sortedByX[middle_index]
  34.  
  35.   #  BASE CASE
  36.   if(point_count == 2):
  37.     return bruteForce(sortedByX)
  38.  
  39.   if point_count == 2:
  40.         return dist(sortedByX[0], sortedByX[1])
  41.   if point_count == 1 or point_count == 0:
  42.       return sys.maxsize
  43.  
  44.   # Divide problem space into left and right
  45.   left = sortedByX[:middle_index]
  46.   right = sortedByX[middle_index:]
  47.  
  48.   leftY = sortedByY[:middle_index]
  49.   rightY = sortedByY[middle_index:]
  50.  
  51.   smallest_distance_left = splitPoints(left, leftY, current_smallest_distance, depth + 1)
  52.   smallest_distance = min(smallest_distance_left, current_smallest_distance)
  53.   smallest_distance_right = splitPoints(right, rightY, smallest_distance, depth + 1)
  54.  
  55.   smallest_distance = min(smallest_distance, smallest_distance_right)
  56.   # if(smallest_distance == 0):
  57.   #   # print(smallest_distance, smallest_distance_right, smallest_distance_left, current_smallest_distance)
  58.   #   sys.exit()
  59.  
  60.   # O(n) Merge them back together
  61.   # start_time_merge = datetime.now()
  62.   middle_boundery = smallest_distance
  63.  
  64.   stripe_points = [x for x in sortedByY if abs(x[0] - middle_point[0]) < middle_boundery]
  65.  
  66.   # time_elapsed_merge = datetime.now() - start_time_merge
  67.   # print('Merge (ms) {}'.format(time_elapsed_merge))
  68.   # print("smallest distance ", smallest_distance)
  69.   # print(stripe_points)
  70.  
  71.   # print("Smallest distance is ", smallest_distance, " WITH ", len(stripe_points), " points in stripe out of ", point_count)
  72.   # print(middle_point)
  73.   # print(stripe_points)
  74.   # O(n) Check stripe
  75.   for i in range(len(stripe_points)):
  76.     start_time = datetime.now()
  77.     for j in range(i + 1, min(i + 7, len(stripe_points))):
  78.       if(i + j < len(stripe_points)):
  79.         stripe_distance = stripe_points[i + j][1] - stripe_points[i][1]
  80.         if(stripe_distance < smallest_distance and stripe_distance != 0):
  81.           smallest_distance = min(smallest_distance, dist(stripe_points[i], stripe_points[i+j]))
  82.     time_elapsed = datetime.now() - start_time
  83.     # print('Stripe check (ms) {}'.format(time_elapsed))
  84.   return smallest_distance
  85.  
  86.  
  87.  
  88. points = []
  89.  
  90. while(True):
  91.     predecessor = (sys.stdin.readline().rstrip("\n"))
  92.     # if line is blank, we leave
  93.     if(predecessor == ''):
  94.         break
  95.     cord_pair = list(map(int, predecessor.split()))
  96.     points.append(cord_pair)
  97.  
  98. sortedByX = sorted(points, key=lambda x: x[0])
  99. sortedByY = sorted(points, key=lambda x: x[1])
  100.  
  101. print(splitPoints(sortedByX, sortedByY, sys.maxsize, 0))
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top