C++ Programming Code Examples C++ > Mathematics Code Examples Program to Find Closest Pair of Points in an Array Program to Find Closest Pair of Points in an Array #include <iostream> #include <cfloat> #include <cstdlib> #include <cmath> using namespace std; /* Point Declaration */ struct Point { int x, y; }; /* sort array of points according to X coordinate */ int compareX(const void* a, const void* b) { Point *p1 = (Point *)a, *p2 = (Point *)b; return (p1->x - p2->x); } /* sort array of points according to Y coordinate */ int compareY(const void* a, const void* b) { Point *p1 = (Point *)a, *p2 = (Point *)b; return (p1->y - p2->y); } /* find the distance between two points */ float dist(Point p1, Point p2) { return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)); } /* return the smallest distance between two points */ float small_dist(Point P[], int n) { float min = FLT_MAX; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (dist(P[i], P[j]) < min) min = dist(P[i], P[j]); } } return min; } /* find the distance beween the closest points of strip of given size */ float stripClosest(Point strip[], int size, float d) { float min = d; for (int i = 0; i < size; ++i) { for (int j = i + 1; j < size && (strip[j].y - strip[i].y) < min; ++j) { if (dist(strip[i],strip[j]) < min) min = dist(strip[i], strip[j]); } } return min; } /* find the smallest distance. */ float closestUtil(Point Px[], Point Py[], int n) { if (n <= 3) return small_dist(Px, n); int mid = n / 2; Point midPoint = Px[mid]; Point Pyl[mid + 1]; Point Pyr[n - mid - 1]; int li = 0, ri = 0; for (int i = 0; i < n; i++) { if (Py[i].x <= midPoint.x) Pyl[li++] = Py[i]; else Pyr[ri++] = Py[i]; } float dl = closestUtil(Px, Pyl, mid); float dr = closestUtil(Px + mid, Pyr, n-mid); float d = min(dl, dr); Point strip[n]; int j = 0; for (int i = 0; i < n; i++) { if (abs(Py[i].x - midPoint.x) < d) strip[j] = Py[i], j++; } return min(d, stripClosest(strip, j, d)); } /* finds the smallest distance */ float closest(Point P[], int n) { Point Px[n]; Point Py[n]; for (int i = 0; i < n; i++) { Px[i] = P[i]; Py[i] = P[i]; } qsort(Px, n, sizeof(Point), compareX); qsort(Py, n, sizeof(Point), compareY); return closestUtil(Px, Py, n); } /* Main */ int main() { Point P[] = {{4, 8}, {13, 38}, {44, 50}, {8, 3}, {14, 9}, {5, 8}}; int n = sizeof(P) / sizeof(P[0]); cout << "The smallest distance is " << closest(P, n); return 0; }