C++ Program to Find Closest Pair of Points in an Array

This C++ Program Finds the Closest Pair of Points in an Array.

Here is source code of the C++ Program to Find the Closest Pair of Points in an Array. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/* 
```

 * C++ 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[] = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};

```
    int n = sizeof(P) / sizeof(P[0]);
```

    cout << "The smallest distance is " << closest(P, n);

```
    return 0;
```
```
}
```

$ g++ closest_pair.cpp
$ a.out
 
The smallest distance is 1.41421
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

If you wish to look at all C++ Programming examples, go to C++ Programs.

If you find any mistake above, kindly email to [email protected]

« Prev - C++ Program to Implement Bit Array

» Next - C++ Program to Check if a Matrix is an Identity Matrix

Related Posts:

Recommended Articles: