Last Updated: 31 Jul, 2020
Day 4 : Closest Distance Pair
Easy
Asked in companies
You are given an array containing 'N' points in the plane. The task is to find out the distance of the closest points.
Note :
Where distance between two points (x1, y1) and (x2, y2) is calculated as [(x1 - x2) ^ 2] + [(y1 - y2) ^ 2].
Input Format :
The first line contains a single integer 'N' denoting the number of points.
The next 'N' lines contain two integers separated by a single space, where the first integer represents the x coordinate and the second integer represents the y coordinate.
Output Format :
The only line contains the minimum distance between the 'N' points.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
2 <= 'N' <= 10^5
-10^5 <= 'x' <= 10^5
-10^5 <= 'y' <= 10^5
Time Limit: 1 sec
Approaches
- For every pair of points (x1, y1) and (x2, y2), calculate the distance by the following formula:
distance = (x1-x2)^2 + (y1-y2)^2. - And if the minimum distance till now is greater than distance then update the minimum distance.
- Return the minimum distance.
We will use the Divide and Conquer Algorithm
- Sort the points with respect to x coordinate and store it in the Pair array.
- Find the middle point in the sorted array, we can take Pair[n/2] as the middle point.
- Divide the given array into two halves. The first subarray contains points from Pair[0] to Pair[n/2]. The second subarray contains points from Pair[n/2+1] to Pair[n-1].
- Recursively find the smallest distances in both subarrays. Let the distances be leftDistance and rightDistance. Find the minimum of both. Let the minimum be minDistance. Our answer is this minDistance if both points of closest distance lie in any one half.
- Now we need to consider the pairs such that one point in the pair is from the left half and the other is from the right half. We will only consider those pairs of points which have a distance less than minDistance as we have already our minimum as minDistance.
- Consider the vertical line passing through the middle point and find all points whose x coordinate is closer than minDistance to the middle vertical line. Build an array Arr of all such points.
- Sort the array Arr according to y coordinates then for each point pi ∈ Arr consider all points pj which have y coordinates less than y coordinates of pi + minDistance, and for each pair calculate the distance and compare with the current best distance.
- At first glance, this is still a non-optimal algorithm: it seems that the number of pj for each pi which have y coordinates less than y coordinates of pi + minDistance will be of order N, and the required asymptotics will not work. However, surprisingly, it can be proved that the number of pairs is a quantity O(1), i.e. it does not exceed some small constant regardless of the points themselves. Proof of this fact can be found here - https://cp-algorithms.com/geometry/nearest_points.html
- Then return the minimum distance.
Similar problems