C++实现使用分治法寻找最近点对

示例输入： 2 3 1 1 2 1 3 5 10 851644 996635 20388 842736 262145 615142 890041 434439 787213 89181 99282 310353 179500 803495 728862 687090 225650 604015 765534 465397

示例输出： 1.00 38153.57

思路及代码：

//
//  main.cpp
//  NearestNodes
//
//  Created by 胡昱 on 2021/10/24.
//

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

// 表示点的结构体
struct Node {
          
   
    int x = 0;
    int y = 0;
};


// 根据横坐标从小到大排序，如果横坐标一样则按纵坐标从小到大排序
bool sortByX(Node& p, Node& q) {
          
   
    if(p.x == q.x) {
          
   
        return p.y < q.y;
    }
    else {
          
   
        return p.x < q.x;
    }
}

// 根据纵坐标从小到大排序，如果纵坐标一样则按横坐标从小到大排序
bool sortByY(Node& p, Node& q) {
          
   
    if(p.y == q.y) {
          
   
        return p.x < q.x;
    }
    else {
          
   
        return p.y < q.y;
    }
}

// 计算两个点之间的距离
double getDistance(Node& p, Node& q) {
          
   
    return sqrt(1.0 * pow((p.x - q.x), 2) + 1.0 * pow((p.y - q.y), 2));
}

// 使用分治法来寻找最近点对的距离
// 输入为一个已排好序的点数组以及开始下标和结束下标
double getShortestDistance(Node* a, int low, int high) {
          
   
    
    double shortestDistance;
    
    int aLength = high - low + 1;
    if(aLength <= 1) {
          
   
        shortestDistance = ((long long int)2) << 60;
    }
    // 如果只有两个点则不用进行分治法了
    else if(aLength == 2) {
          
   
        shortestDistance = getDistance(a[0], a[1]);
    }
    
    // 如果只剩三个点也不用进行分治法了
    else if(aLength == 3) {
          
   
        shortestDistance = min(min(getDistance(a[0], a[1]), getDistance(a[0], a[2])), getDistance(a[1], a[2]));
    }
    
    // 如果大于三个点则需要继续使用分治法
    else {
          
   
        
        // 分解成左右两个区域，并得到左右两个区域各自的最近点对距离
        int mid = (low + high) / 2;
        shortestDistance = min(getShortestDistance(a, low, mid), getShortestDistance(a, mid + 1, high));
        
        // 对子问题进行归并，即判断左区域中的点与右区域中的点是否会构成更短的距离
        // 只有横坐标与mid点横坐标的距离小于shortestDistance的点才有可能与另一个子区域的点构成最近点对
        Node* possibleNodes = new Node[aLength];
        int possibleNum = 0;
        for(int i = low; i < high; ++i) {
          
   
            if(abs(a[i].x - a[mid].x) < shortestDistance) {
          
   
                possibleNodes[possibleNum] = a[i];
                ++possibleNum;
            }
        }
        // 按照纵坐标进行排序以减少比较次数
        sort(possibleNodes, possibleNodes + possibleNum, sortByY);
        // 开始比较可能是跨区域的最近点对之间的距离
        for(int i = 0; i < possibleNum - 1; ++i) {
          
   
            for(int j = i + 1; j < possibleNum; ++j) {
          
   
                // 如果j点的纵坐标与i点的纵坐标的差距已经超过目前的最短距离，则剩下的点就不用比较了
                if(possibleNodes[j].y - possibleNodes[i].y > shortestDistance) {
          
   
                    break;
                }
                else {
          
   
                    shortestDistance = min(shortestDistance, getDistance(possibleNodes[i], possibleNodes[j]));
                }
            }
        }
        
        // 释放资源
        delete [] possibleNodes;
    }
    
    return shortestDistance;
}

int main(int argc, const char * argv[]) {
          
   
    // 共有m个问题
    int m;
    cin >> m;
    while((m--) > 0) {
          
   
        
        // 输入坐标
        int n;
        cin >> n;
        Node* a = new Node[n];
        for(int i = 0; i < n; ++i) {
          
   
            cin >> a[i].x >> a[i].y;
        }
        
        // 根据横坐标从小到大排序
        sort(a, a + n, sortByX);
        
        // 寻找最近点对并输出结果
        printf("%.2lf
", getShortestDistance(a, 0, n - 1));
        
        // 释放资源
        delete [] a;
    }
    return 0;
}