Consider ‘N’ points in an XY- plane. Develop an algorithm and python code to determine the pair of points that are closer. Distance between two points (x1, y1) and (x2, y2) is determined using the formula. code example

Example: how to find closest distance for given points

# A divide and conquer program in Python3 
# to find the smallest distance from a 
# given set of points. 
import math 
import copy 
# A class to represent a Point in 2D plane 
class Point(): 
	def __init__(self, x, y): 
		self.x = x 
		self.y = y 

# A utility function to find the 
# distance between two points 
def dist(p1, p2): 
	return math.sqrt((p1.x - p2.x) *
					(p1.x - p2.x) +
					(p1.y - p2.y) *
					(p1.y - p2.y)) 

# A Brute Force method to return the 
# smallest distance between two points 
# in P[] of size n 
def bruteForce(P, n): 
	min_val = float('inf') 
	for i in range(n): 
		for j in range(i + 1, n): 
			if dist(P[i], P[j]) < min_val: 
				min_val = dist(P[i], P[j]) 

	return min_val 

# A utility function to find the 
# distance beween the closest points of 
# strip of given size. All points in 
# strip[] are sorted accordint to 
# y coordinate. They all have an upper 
# bound on minimum distance as d. 
# Note that this method seems to be 
# a O(n^2) method, but it's a O(n) 
# method as the inner loop runs at most 6 times 
def stripClosest(strip, size, d): 
	
	# Initialize the minimum distance as d 
	min_val = d 

	
	# Pick all points one by one and 
	# try the next points till the difference 
	# between y coordinates is smaller than d. 
	# This is a proven fact that this loop 
	# runs at most 6 times 
	for i in range(size): 
		j = i + 1
		while j < size and (strip[j].y -
							strip[i].y) < min_val: 
			min_val = dist(strip[i], strip[j]) 
			j += 1

	return min_val 

# A recursive function to find the 
# smallest distance. The array P contains 
# all points sorted according to x coordinate 
def closestUtil(P, Q, n): 
	
	# If there are 2 or 3 points, 
	# then use brute force 
	if n <= 3: 
		return bruteForce(P, n) 

	# Find the middle point 
	mid = n // 2
	midPoint = P[mid] 

	# Consider the vertical line passing 
	# through the middle point calculate 
	# the smallest distance dl on left 
	# of middle point and dr on right side 
	dl = closestUtil(P[:mid], Q, mid) 
	dr = closestUtil(P[mid:], Q, n - mid) 

	# Find the smaller of two distances 
	d = min(dl, dr) 

	# Build an array strip[] that contains 
	# points close (closer than d) 
	# to the line passing through the middle point 
	strip = [] 
	for i in range(n): 
		if abs(Q[i].x - midPoint.x) < d: 
			strip.append(Q[i]) 

	# Find the closest points in strip. 
	# Return the minimum of d and closest 
	# distance is strip[] 
	return min(d, stripClosest(strip, len(strip), d)) 

# The main function that finds 
# the smallest distance. 
# This method mainly uses closestUtil() 
def closest(P, n): 
	P.sort(key = lambda point: point.x) 
	Q = copy.deepcopy(P) 
	Q.sort(key = lambda point: point.y)	 

	# Use recursive function closestUtil() 
	# to find the smallest distance 
	return closestUtil(P, Q, n) 

# Driver code 
P = [Point(2, 3), Point(12, 30), 
	Point(40, 50), Point(5, 1), 
	Point(12, 10), Point(3, 4)] 
n = len(P) 
print("The smallest distance is", 
				closest(P, n)) 

# This code is contributed 
# by Prateek Gupta (@prateekgupta10)