printing the closest pair of points

Question

I was writing this code to find the minimum distance between 2 points.The code I have written gives me the minimum distance correctly but does not give the correct coordinates from which the minimum distance is computed.Kindly help me identify the problem according to me this is the correct approach to print the points as well along with the minimum distance.

#include<bits/stdc++.h>
#define FOR(i,N) for(int i=0;i<(N);i++)
#define rep(i,a,n) for(int i=(a);i<(n);i++)
using namespace std;
struct point {
int x;
int y;
};

typedef struct point point;
void printarr(point arr[], int n) {for(int i = 0; i < n; i++) cout <<                   
arr[i].x << " " << arr[i].y << endl; cout << endl; 
bool comparex(const point& X, const point& Y) { return X.x < Y.x; }
bool comparey(const point& X, const point& Y) { return X.y < Y.y; }

float getdis(point X, point Y) { return sqrt((X.x - Y.x)*(X.x - Y.x) + (X.y         
- Y.y)*(X.y - Y.y)); }
float brutedis(point P[], int n, point A[]) {
float d = INT_MAX;
float temp;
FOR(i, n) {
    rep(j, i+1, n) {
        temp = getdis(P[i],P[j]);
        if(temp < d) {
            d = temp;
            A[0].x = P[i].x; A[0].y = P[i].y;
            A[1].x = P[j].x ; A[1].y = P[j].y;
        }
    }
}
return d;
}

float stripdis(point P[], int n, float d, point A[]) {
float temp = d;
float dis;
sort(P, P + n, comparey);
FOR(i, n) {
    rep(j,i+1,n) {
        if(abs(P[j].y - P[i].y) < d) {
            dis = getdis(P[j], P[i]);
            if(dis < temp) {
                temp = dis;
                A[0].x = P[i].x; A[0].y = P[i].y;
                A[1].x = P[j].x ; A[1].y = P[j].y;
            }
        }
    }
  }
   return temp;
   }

  float solve(point P[], int n, point A[]) {

  if(n <= 3) return brutedis(P, n, A);

  int mid = n/2;
  point M = P[mid];
 float d = min(solve(P, mid, A), solve(P+mid, n-mid, A));
point strip[n];
int j = 0;
int i = 0;
while(i < n) {
    if(abs(P[i].x - M.x) < d) strip[j++] = P[i];
    i++;
}

return min(d, stripdis(strip, j, d, A));
 }

 int main() {

point P[] = {{0, 0}, {-4,1}, {-7, -2}, {4, 5}, {1, 1}};
int n = sizeof(P) / sizeof(P[0]);
sort(P, P+n, comparex);
point A[2];
cout << "Minimum Distance = " << solve(P, n, A) << "\n";
printarr(A, 2);
//printarr(P, n);
return 0;
}

Answer 1

You call solve twice, both giving it A as the parameter. Each of these calls always overwrite A, but only one returns the correct answer. And they both call brutedis that also always overwrites A.

The easiest way to fix this is to introduce an additional parameter to all these functions, that would contain the minimal distance found so far, the same way you did with stripdis.

float solve(point P[], int n, float d, point A[]) {

  if(n <= 3) return brutedis(P, n, d, A);

    ...
    d = solve(P, mid, d, A);
    d = solve(P+mid, n-mid, d, A);

    d = stripdis(strip, j, d, A));

...


float brutedis(point P[], int n, float d, point A[])
{
  // float d = INT_MAX -- Not needed

Thus A will only be overeritten if the distance between the new pair of points is globally minimal so far.

No need to call min as each function already keeps the minimum of d and the distance it finds.