Guest User

v7.1

a guest
Aug 21st, 2019
97
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