如何基于vector实现每个点的最近邻查找（仅修改main函数）

核心实现思路 #

通过嵌套循环遍历所有点对，借助已重载的operator-计算点间距离平方，为每个点记录最小距离对应的最近邻。需注意跳过点自身的比较，避免无意义的计算。

补充完整的main函数代码 #

假设已有Point类、createPointsList（读取用户输入生成点列表）、displayPoints（输出点信息）函数，补充后的完整代码如下：

#include <iostream>
#include <vector>
#include <climits>

// 题目已提供的Point类（含重载operator-）
struct Point {
    int x, y;
    int operator-(const Point& other) const {
        int dx = x - other.x;
        int dy = y - other.y;
        return dx*dx + dy*dy;
    }
};

// 题目提供的输入函数
std::vector<Point> createPointsList() {
    std::vector<Point> points;
    int n;
    std::cout << "请输入点的数量: ";
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        Point p;
        std::cout << "请输入第" << i+1 << "个点的x和y坐标: ";
        std::cin >> p.x >> p.y;
        points.push_back(p);
    }
    return points;
}

// 题目提供的输出函数
void displayPoints(const std::vector<Point>& points) {
    std::cout << "点列表:\n";
    for (size_t i = 0; i < points.size(); ++i) {
        std::cout << "点" << i+1 << ": (" << points[i].x << ", " << points[i].y << ")\n";
    }
}

int main() {
    std::vector<Point> points = createPointsList();
    displayPoints(points);

    int pointCount = points.size();
    if (pointCount < 2) {
        std::cout << "至少需要2个点才能查找最近邻\n";
        return 0;
    }

    // 存储每个点的最近邻索引、最小距离平方
    std::vector<int> nearestIdx(pointCount);
    std::vector<int> minDistSq(pointCount, INT_MAX);

    // 嵌套循环遍历所有点对
    for (int i = 0; i < pointCount; ++i) {
        for (int j = 0; j < pointCount; ++j) {
            if (i == j) continue; // 跳过自身

            int currentDistSq = points[i] - points[j];
            // 更新最小距离和最近邻
            if (currentDistSq < minDistSq[i]) {
                minDistSq[i] = currentDistSq;
                nearestIdx[i] = j;
            }
        }
    }

    // 输出结果
    std::cout << "\n每个点的最近邻:\n";
    for (int i = 0; i < pointCount; ++i) {
        int neighborIdx = nearestIdx[i];
        std::cout << "点" << i+1 << " (" << points[i].x << ", " << points[i].y << ") 的最近邻是点" 
                  << neighborIdx+1 << " (" << points[neighborIdx].x << ", " << points[neighborIdx].y 
                  << ")，距离平方为" << minDistSq[i] << "\n";
    }

    return 0;
}

关键代码说明 #

• 嵌套循环逻辑：外层循环遍历目标点i，内层循环遍历所有其他点j，跳过i==j的情况避免无效计算。
• 距离计算优化：直接使用重载的operator-获取距离平方，无需开根号，既提升效率又不影响最小距离的判断。
• 边界处理：当点数量不足2时，直接提示无法查找，避免程序逻辑错误。

示例输入输出 #

输入：
请输入点的数量: 3
请输入第1个点的x和y坐标: 0 0
请输入第2个点的x和y坐标: 1 1
请输入第3个点的x和y坐标: 3 3

输出：
点列表:
点1: (0, 0)
点2: (1, 1)
点3: (3, 3)

每个点的最近邻:
点1 (0, 0) 的最近邻是点2 (1, 1)，距离平方为2
点2 (1, 1) 的最近邻是点1 (0, 0)，距离平方为2
点3 (3, 3) 的最近邻是点2 (1, 1)，距离平方为8

内容的提问来源于stack exchange，提问作者dyinng