how to find closest distance for given points

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