c++ - 尝试查找数组中点之间的最小距离时随机垃圾输出

Question

有什么大惊小怪的？

我试图找到点之间的最小距离(2D 平面中两点之间的距离:从 (x1, y1) 到 (y1, y2)) 的距离，它们被存储在数组 arr 中，然后计算并返回这些距离的最小值。

但是，问题是我的源代码产生随机垃圾输出。

想法是通过以下公式获取点 (x1, y1) 和 (x2, y2) 之间的距离: sqrt((x1 - x2)^2 + (y1 - y2)^2)。 为此，我为每次迭代选择了 4 个元素: x1 = arr[0], x2 = arr[1], y1 = arr[2], y2 = arr[3]。 x1 和 x2 对于每次迭代(i)保持不变，而 x1, x2 和 之间的距离>y1, y2(随着 j 的每次唯一迭代而变化)被计算出来。最后，选择两点之间的最短距离返回给main()。

我做了什么来解决这个烂摊子？

在源代码中包含调试语句表明，罪魁祸首是随机垃圾值(从字面上看，它甚至不应该存在!)。

另一个罪魁祸首是 sqrt(arg) 给出了一个随机的垃圾值。例如计算(4, 4)和(1, 100)的距离时，结果为sqrt(0 + (-99)^2 ) = 99。但它会输出 -2147483648。

这是我的代码:

#include<iostream>
#include<vector>
#include<cmath>
using std::sqrt;
using std::cin;
using std::cout;
using std::endl;
using std::vector;
int dist_cal(vector<int>&, int);

int main()
{
    int num_pairs = -1;
    cout << "Enter the number of pairs of point co-ordinates (x, y) that you want to enter: " << endl;
    cin >> num_pairs;

    vector<int> points;
    cout << "Now enter the (x, y) co-ordinate pairs: " << endl;
    for (int i = 0; i < num_pairs * 2; i++)
    {
        int buff;
        cin >> buff;
        points.push_back(buff);
    }

    cout << "The minimum distance between the array of points entered is " << dist_cal(points, num_pairs) << "." << endl;
    return 0;
}

int dist_cal(vector<int>& arr, int num_pairs)
{
    int min_distance = -1, temp_distance = -1, x1, x2, y1, y2, itr_count = 0;
    for (int i = 0; i <= num_pairs; i += 2)
    {
        x1 = arr[i + 0];
        x2 = arr[i + 1];
        for (int j = i + 2; j <= num_pairs; j += 2)
        {
            y1 = arr[j + 0];
            y2 = arr[j + 1];
            temp_distance = sqrt((x1 - x2)^2 + (y1 - y2)^2);
            if (itr_count == 0)
            {
                min_distance = temp_distance;
                itr_count++;
            }
            if (min_distance > temp_distance)
            {
                min_distance = temp_distance;
            }
        }
    }
    return min_distance;
}

我知道这种方法很朴素并且复杂度为 O(n^2)，但要转向更快的算法，我必须首先使用最基本的心理健全方法解决它。

对于输入:

4
4 4
7 8
1 100
4 4

输出应该是0。

实际输出如下: 输入的点数组之间的最小距离是 -2147483648。

我在这里做错了什么？也欢迎替代(和更有效的算法)!提前致谢! :)

Answer 1

在C++中^表示异或按位运算，如果想对x1-x2进行2的次方运算，可以这样写:(x1-x2 ) * (x1 - x2) 或使用 std::pow 函数。

所以这个

sqrt((x1 - x2)^2 + (y1 - y2)^2);

应该是:

sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));

---

另一个问题，sqrt 返回实数，所以 min_distance 和 temp_distance 应该是 double 或 float 。

---

您的 vector 以这种形式保存坐标:x(i),y(i),..

这样读

    x1 = arr[i + 0];
    x2 = arr[i + 1];

是错误的，应该是:

    x1 = arr[i + 0];
    y1 = arr[i + 1];

在内部循环中做同样的事情。

---

此外，您的内部循环应从 0 索引开始。并且您必须检测到针对给定的 p 点计算 distance(p,p)(它始终为 0)并跳过此迭代的情况。然后您将计算所有距离。