C++编写穷举法算法求解最近点对问题代码

在C++中，穷举法常常用于解决一些简单的问题，比如寻找两个集合之间的最近点对问题。这个问题可以理解为在一个二维数组（或点集）中找到两个元素，使得它们之间的曼哈顿距离（水平距离加上垂直距离）最小。

以下是一个简单的C++代码示例，展示了如何使用穷举法来解决这个问题：

#include <iostream>
#include <vector>
using namespace std;

int manhattanDistance(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}

pair<int, pair<int, int>> closestPair(vector<pair<int, int>>& points) {
    int n = points.size();
    if (n <= 1) return {-1, {0, 0}}; // 如果点的数量小于等于1，没有近似点对

    int min_dist = INT_MAX;
    int x_min, y_min;

    for (int i = 0; i < n; ++i) {
        for (int j = i+1; j < n; ++j) {
            int dist = manhattanDistance(points[i].first, points[i].second, points[j].first, points[j].second);
            if (dist < min_dist) {
                min_dist = dist;
                x_min = points[i].first;
                y_min = points[i].second;
            }
        }
    }

    return {min_dist, {x_min, y_min}};
}

int main() {
    vector<pair<int, int>> points = {{1, 3}, {3, 4}, {5, 6}, {7, 8}};
    auto result = closestPair(points);
    cout << "The closest pair has a distance of " << result.first << ", located at (" << result.second.first << ", " << result.second.second << ")." << endl;
    return 0;
}

这个程序首先检查点的数量，然后遍历所有可能的点对，并计算它们之间的曼哈顿距离。每次更新当前找到的最短距离和对应坐标。当遍历结束后，返回找到的最近点对及其距离。