C++信息学奥赛

问题描述：给定平面上n个点，找到距离最近的一对点。这是计算几何中的经典问题，分治算法可以高效地解决这个问题。

解题思路：

最近点对问题的分治解法将平面上的点分为左右两部分，分别求解左右两部分的最近点对，然后检查是否存在跨越两部分的更近点对。

1. 分解：将点集按x坐标排序，分为左右两个子集
2. 解决：
   • 递归求解左子集的最近点对及距离d1
   • 递归求解右子集的最近点对及距离d2
   • 令d = min(d1, d2)，检查在距离分割线d范围内的点是否存在更近的点对
3. 合并：返回d和跨越点对距离中的最小值

代码实现

// 最近点对问题的分治实现
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>
using namespace std;

// 定义点结构
struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
};

// 计算两点之间的距离
double distance(const Point& a, const Point& b) {
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx*dx + dy*dy);
}

// 按x坐标排序
bool compareX(const Point& a, const Point& b) {
    return a.x < b.x;
}

// 按y坐标排序
bool compareY(const Point& a, const Point& b) {
    return a.y < b.y;
}

// 暴力求解最近点对距离（用于小规模点集）
double bruteForce(const vector<Point>& points, int left, int right) {
    double minDist = numeric_limits<double>::max();
    for (int i = left; i <= right; i++) {
        for (int j = i + 1; j <= right; j++) {
            minDist = min(minDist, distance(points[i], points[j]));
        }
    }
    return minDist;
}

// 寻找跨越左右两部分的最近点对
double closestCrossing(const vector<Point>& points, int left, int mid, int right, double d) {
    vector<Point> strip;
    double midX = points[mid].x;
    
    // 收集距离中线小于d的点
    for (int i = left; i <= right; i++) {
        if (abs(points[i].x - midX) < d) {
            strip.push_back(points[i]);
        }
    }
    
    // 按y坐标排序
    sort(strip.begin(), strip.end(), compareY);
    
    // 检查每个点与后续最多6个点的距离
    double minDist = d;
    int n = strip.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n && (strip[j].y - strip[i].y) < minDist; j++) {
            minDist = min(minDist, distance(strip[i], strip[j]));
        }
    }
    
    return minDist;
}

// 分治算法求解最近点对
double closestUtil(const vector<Point>& points, int left, int right) {
    // 基本情况：点的数量较少时，使用暴力法
    if (right - left + 1 <= 3) {
        return bruteForce(points, left, right);
    }
    
    // 分解：找到中间点
    int mid = left + (right - left) / 2;
    Point midPoint = points[mid];
    
    // 解决：递归求解左右两部分
    double leftDist = closestUtil(points, left, mid);
    double rightDist = closestUtil(points, mid + 1, right);
    
    // 找到左右两部分中的最小距离
    double d = min(leftDist, rightDist);
    
    // 检查跨越左右两部分的点对
    double crossDist = closestCrossing(points, left, mid, right, d);
    
    // 合并：返回三者中的最小值
    return min(d, crossDist);
}

// 计算最近点对距离
double closestPair(vector<Point> points) {
    // 先按x坐标排序
    sort(points.begin(), points.end(), compareX);
    return closestUtil(points, 0, points.size() - 1);
}

int main() {
    vector<Point> points = {
        Point(2, 3), Point(12, 30), Point(40, 50), 
        Point(5, 1), Point(12, 10), Point(3, 4)
    };
    
    cout << "点的数量: " << points.size() << endl;
    cout << "最近点对的距离: " << closestPair(points) << endl;
    
    return 0;
}