Resources:
cp-algorithms
Closest Pair of Points
Closest Pair of Points Problem
concept another explanation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<bits/stdc++.h> | |
| using namespace std; | |
| struct point | |
| { | |
| int x,y; | |
| }; | |
| int cmpX(point a, point b) | |
| { | |
| return (a.x < b.x); | |
| } | |
| int cmpY(point a, point b) | |
| { | |
| return (a.y < b.y); | |
| } | |
| float dist(point a, point b) | |
| { | |
| return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); | |
| } | |
| float findMinDist(point pts[], int n) | |
| { | |
| float mn = 99999.0; | |
| for(int i = 0; i < n; i++) | |
| for(int j = i+1; j < n; j++) | |
| if(dist(pts[i], pts[j]) < mn) | |
| mn = dist(pts[i], pts[j]); | |
| return mn; | |
| } | |
| float MIN(float a, float b) | |
| { | |
| return (a < b) ? a : b; | |
| } | |
| float stripClose(point strip[], int sz, float d) | |
| { | |
| float mn = d; | |
| for(int i = 0 ; i < sz; i++) | |
| for(int j = i+1; j < sz && (strip[j].y - strip[i].y) < mn; j++) | |
| if( dist(strip[i], strip[j] ) < mn) | |
| mn = dist(strip[i], strip[j]); | |
| return mn; | |
| } | |
| float findClosest(point xSorted[], point ySorted[], int n) | |
| { | |
| if(n <= 3) | |
| return findMinDist(xSorted, n); | |
| int mid = n/2; | |
| point midPoint = xSorted[mid]; | |
| point ySortedLeft[mid+1]; // y sorted point in the left side | |
| point ySortedRight[n-mid-1]; // y sorted in the right side. | |
| int leftIdx = 0, RightIdx = 0; | |
| for(int i = 0; i < n; i++){ | |
| if(ySorted[i].x <= midPoint.x) | |
| ySortedLeft[leftIdx++] = ySorted[i]; | |
| else | |
| ySortedRight[RightIdx++] = ySorted[i]; | |
| } | |
| float leftDist = findClosest(xSorted, ySorted, mid); | |
| float rightDist = findClosest(xSorted, ySorted,n - mid); | |
| float dist = min(leftDist, rightDist); | |
| point strip[n]; // hold points closer to the vertical line. | |
| int j = 0; | |
| for(int i = 0; i < n; i++) | |
| if(abs(ySorted[i].x - midPoint.x) < dist){ | |
| strip[j++] = ySorted[i]; | |
| } | |
| return min(dist, stripClose(strip,j,dist)); // find minimum using dist and closest pair in strip. | |
| } | |
| float closestPair(point pts[], int n) | |
| { | |
| point xSorted[n]; | |
| point ySorted[n]; | |
| for(int i = 0; i < n; i++){ | |
| xSorted[i] = pts[i]; | |
| ySorted[i] = pts[i]; | |
| } | |
| sort(xSorted, xSorted+n,cmpX); | |
| sort(ySorted, ySorted+n, cmpY); | |
| return findClosest(xSorted, ySorted, n); | |
| } | |
| int main() | |
| { | |
| ios_base::sync_with_stdio(false); | |
| cin.tie(0); | |
| point P[] ={{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}}; | |
| int n = sizeof(P) / sizeof(P[0]); | |
| cout<< "The minimum distance is " <<closestPair(P, n)<<endl; | |
| } |
No comments:
Post a Comment