最近点对问题c++蛮力法

最近点对问题（Closest Pair of Points Problem），简称CP，是一个经典的计算机科学问题，通常涉及到计算二维空间中的一组点对中最接近的一对。在C++中，蛮力法（Brute Force）是一种简单直接但效率较低的解题策略，它尝试所有可能的点对组合，通过比较它们之间的距离来找到最短的距离。

以下是使用C++蛮力法求解最近点对的基本步骤：

1. 定义一个结构体或类来表示点，包含两个浮点数（x坐标和y坐标）。
2. 将所有的点存储在一个数组或集合中。
3. 使用两层嵌套循环遍历所有的点对，每次外层循环代表第一个点，内层循环代表第二个点。
4. 计算每个点对之间的欧几里得距离，并记录下当前发现的最小距离以及对应的点对。
5. 当所有点对都检查完后，返回找到的最近点对及其距离。

#include <iostream>
#include <cmath>

// 定义点结构
struct Point {
    double x, y;
};

double euclidean_distance(const Point &p1, const Point &p2) {
    return std::sqrt(std::pow(p1.x - p2.x, 2) + std::pow(p1.y - p2.y, 2));
}

Point closest_pair(const Point points[], int n) {
    if (n <= 1) return {0, 0}; // 如果只剩一个或没有点，返回任意一对
    double min_dist = std::numeric_limits<double>::max();
    Point closest_points;

    for (int i = 0; i < n - 1; ++i) { // 遍历第一层
        for (int j = i + 1; j < n; ++j) { // 遍历第二层
            double dist = euclidean_distance(points[i], points[j]);
            if (dist < min_dist) {
                min_dist = dist;
                closest_points = {points[i].x, points[j].y};
            }
        }
    }

    return closest_points;
}

int main() {
    Point points[] = {{1, 2}, {3, 4}, {6, 8}, {5, 9}};
    int n = sizeof(points) / sizeof(points[0]);

    Point result = closest_pair(points, n);
    std::cout << "The closest pair is (" << result.x << ", " << result.y << ") with a distance of " << min_dist << std::endl;

    return 0;
}