打印最近的一对点

Question

我写这段代码是为了找到 2 之间的最小距离 points.The 我写的代码正确地给出了最小距离，但没有给出最小距离为 computed.Kindly帮助我根据我确定问题这是打印点以及最小距离的正确方法。

#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

在某种程度上我可以遵循你格式错误的代码，brutedis 无条件修改 A[] 并且在你找到正确答案后再次调用它（但不知道你找到了正确答案）。

所以如果第一个调用在 min(solve(P, mid, A), solve(P+mid, n-mid, A)); 中最好，第二个仍然可以调用 brutedis 并销毁 A[]

Answer 2

你调用了solve两次，两次都给它A作为参数。这些调用中的每一个都会覆盖 A，但只有一个 returns 是正确答案。他们都称 brutedis 也总是覆盖 A.

解决这个问题的最简单方法是为所有这些函数引入一个附加参数，该参数将包含迄今为止找到的最小距离，就像您对 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

因此，只有当新点对之间的距离到目前为止全局最小时，A 才会被忽略。

无需调用 min，因为每个函数已经保留了 d 的最小值及其找到的距离。

Answer 3

那是因为在 "A" 数组中获得正确的坐标后，您再次更新它。只需在您的代码中查找以下语句：

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

这将给出正确的最小距离但不是正确的坐标。试想一下，如果你第一次调用 solve ，在上面的语句中有最小距离坐标，那么你第二次调用将修改 A[] 中的坐标。拿笔和纸尝试解决你的坐标，它会让你更好地理解。

打印最近的一对点

printing the closest pair of points

c++

divide-and-conquer

output