1# A divide and conquer program in Python3
2# to find the smallest distance from a
3# given set of points.
4import math
5import copy
6# A class to represent a Point in 2D plane
7class Point():
8 def __init__(self, x, y):
9 self.x = x
10 self.y = y
11
12# A utility function to find the
13# distance between two points
14def dist(p1, p2):
15 return math.sqrt((p1.x - p2.x) *
16 (p1.x - p2.x) +
17 (p1.y - p2.y) *
18 (p1.y - p2.y))
19
20# A Brute Force method to return the
21# smallest distance between two points
22# in P[] of size n
23def bruteForce(P, n):
24 min_val = float('inf')
25 for i in range(n):
26 for j in range(i + 1, n):
27 if dist(P[i], P[j]) < min_val:
28 min_val = dist(P[i], P[j])
29
30 return min_val
31
32# A utility function to find the
33# distance beween the closest points of
34# strip of given size. All points in
35# strip[] are sorted accordint to
36# y coordinate. They all have an upper
37# bound on minimum distance as d.
38# Note that this method seems to be
39# a O(n^2) method, but it's a O(n)
40# method as the inner loop runs at most 6 times
41def stripClosest(strip, size, d):
42
43 # Initialize the minimum distance as d
44 min_val = d
45
46
47 # Pick all points one by one and
48 # try the next points till the difference
49 # between y coordinates is smaller than d.
50 # This is a proven fact that this loop
51 # runs at most 6 times
52 for i in range(size):
53 j = i + 1
54 while j < size and (strip[j].y -
55 strip[i].y) < min_val:
56 min_val = dist(strip[i], strip[j])
57 j += 1
58
59 return min_val
60
61# A recursive function to find the
62# smallest distance. The array P contains
63# all points sorted according to x coordinate
64def closestUtil(P, Q, n):
65
66 # If there are 2 or 3 points,
67 # then use brute force
68 if n <= 3:
69 return bruteForce(P, n)
70
71 # Find the middle point
72 mid = n // 2
73 midPoint = P[mid]
74
75 # Consider the vertical line passing
76 # through the middle point calculate
77 # the smallest distance dl on left
78 # of middle point and dr on right side
79 dl = closestUtil(P[:mid], Q, mid)
80 dr = closestUtil(P[mid:], Q, n - mid)
81
82 # Find the smaller of two distances
83 d = min(dl, dr)
84
85 # Build an array strip[] that contains
86 # points close (closer than d)
87 # to the line passing through the middle point
88 strip = []
89 for i in range(n):
90 if abs(Q[i].x - midPoint.x) < d:
91 strip.append(Q[i])
92
93 # Find the closest points in strip.
94 # Return the minimum of d and closest
95 # distance is strip[]
96 return min(d, stripClosest(strip, len(strip), d))
97
98# The main function that finds
99# the smallest distance.
100# This method mainly uses closestUtil()
101def closest(P, n):
102 P.sort(key = lambda point: point.x)
103 Q = copy.deepcopy(P)
104 Q.sort(key = lambda point: point.y)
105
106 # Use recursive function closestUtil()
107 # to find the smallest distance
108 return closestUtil(P, Q, n)
109
110# Driver code
111P = [Point(2, 3), Point(12, 30),
112 Point(40, 50), Point(5, 1),
113 Point(12, 10), Point(3, 4)]
114n = len(P)
115print("The smallest distance is",
116 closest(P, n))
117
118# This code is contributed
119# by Prateek Gupta (@prateekgupta10)
120