# 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):