How to find the closest pair of points within a vector?

Question

I have to write a program that inputs pairs of points from the user and finds the closest neighbor to each point, using the distance formula.

From the instructions I've been given, I must edit only the main() function and add a nested loop to compare each point, but I'm not sure how to do this.

The instructor has also written a function to overload operator- that returns the distance, which I think I'm supposed to use, somehow.

The output should look something like this:

Example input 1

5 1 1 2 2 3 3 4 4 5 5

Example output 1

(1,1) (2,2) (3,3) (4,4) (5,5) 
(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)

This is the main.cpp code:

void displayPoints(vector<Point> &points) {
  // 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

You could use a nested loop and compare each value with the other.

Need to add an if-statement to prevent to compare points to itself.

In your loop, find the smallest distance and show it for the current Point at the end of the outer loop.

The solution is rather straight forward:

#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';
    }
}

Input and output of this program: