如何找到向量中最近的一对点？

Question

所以，我必须编写一个程序，从用户输入成对的点，并使用距离公式找到离它最近的邻居。根据我得到的说明，我必须只编辑主要内容并添加一个嵌套循环来比较每个点，但我不确定如何执行此操作。讲师还编写了一个重载函数——它返回我认为我应该以某种方式使用的距离。

输出应该是这个样子：

示例输入 1

5 1 1 2 2 3 3 4 4 5 5

示例输出 1

(1,1) nearest (2,2)
(2,2) nearest (1,1)
(3,3) nearest (2,2)
(4,4) nearest (3,3)
(5,5) nearest (4,4)

这是main.cpp代码：

  // Finish
  for (int i = 0; i < points.size(); i++) {
    
    cout << points[i] << " ";
  }
  cout <<endl;
}

void createPointsList(vector<Point> &points) {
  int s;
  cin >> s;
  for (int i = 0; i < s; ++i) {
    int x, y;
    cin >> x >> y;
    points.push_back(Point(x, y));
  }
}

int main() {

  vector<Point> points;
  createPointsList(points);
  displayPoints(points);
  // Add code to find nearest here
  // Hint: will need a nested loop to compare each point with every other point

}

//The overloaded operator is :

// d=√((x2 – x1)² + (y2 – y1)²)
double Point::operator-(const Point& point) const { 
    return (pow(point.x-x,2) + pow(point.y-y,2))); 
} `

Answer 1

您可以使用嵌套循环并将每个值与另一个进行比较。

需要添加一个

if

-statement来防止将点与自身进行比较。

在你的循环中，找到最小距离并在外循环结束时显示当前点。

解决方案相当简单：

#include <iostream>
#include <vector>
#include <cmath>
#include <limits>

struct Point {
    double x{};
    double y{};
    friend std::ostream& operator << (std::ostream& os, const Point& p) {
        return os << '(' << p.x << ',' << p.y << ')';
    }
    double operator-(const Point& point) const {
        return (std::pow(point.x - x, 2) + std::pow(point.y - y, 2));
    }
};
void createPointsList(std::vector<Point>& points) {
    int s;
    std::cin >> s;
    for (int i = 0; i < s; ++i) {
        int x, y;
        std::cin >> x >> y;
        points.push_back(Point(x, y));
    }
}
void displayPoints(const std::vector<Point>& points) {
    for (const Point& p : points)
        std::cout << p << '\n';
}

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

    // Add code to find nearest here
    // Hint: will need a nested loop to compare each point with every other point

    for (std::size_t i{}; i < points.size(); ++i) {
        std::size_t nearestIndex{ i };
        double smallestDistance{ std::numeric_limits<double>::max()};

        for (std::size_t k{}; k < points.size(); ++k) {
            if (i != k) {
                const double distance = points[k] - points[i];
                if (distance < smallestDistance) {
                    smallestDistance = distance;
                    nearestIndex = k;
                }
            }
        }
        std::cout << points[i] << " nearest " << points[nearestIndex] << '\n';
    }
}

本程序的输入输出：