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

That is because after getting the correct coordinates in "A" array, you are again updating that. just look for the below statement in your code:

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

this will give correct minimum distance but not correct coordinates. Just think about it, if your first call to solve, in the above statement has the minimum distance coordinates, then your second call is going to modify the coordinates in A[]. take a pen and paper and try to solve for the coordinates you have, it'll give you better understanding.

Answer 2

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.

Answer 3

To the extent I can follow your badly formatted code, brutedis unconditionally modifies A[] and it gets called again after you have found the right answer (but don't know you found the right answer).

So if the first call were best in min(solve(P, mid, A), solve(P+mid, n-mid, A)); the second could still call brutedis and destroy A[]