C++ 实现求解平面上最近点对问题

该程序实现了求解平面上 n 个点中最近点对的问题。首先，程序使用稳定排序算法将点按照 x 坐标进行排序，然后计算相邻点之间的距离，更新最小距离。接着，程序使用稳定排序算法将点按照 y 坐标进行排序，然后再次计算相邻点之间的距离，更新最小距离。最后，输出最小距离。

#include <bits/stdc++.h>
using namespace std;
inline static const nullptr_t _=[](){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr),cout.tie(nullptr);
    return nullptr;
}();
int n;pair<double,double> *a;double mindis=numeric_limits<double>::infinity();
double dist(pair<double,double> a,pair<double,double> b){
	return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}
int main(){
    cin>>n;
    a=new pair<double,double>[n];
    for(int i=0;i<n;i++) cin>>a[i].first>>a[i].second;
    stable_sort(a,a+n);
    for(int i=1;i<n;i++) mindis=min(mindis,dist(a[i],a[i-1]));
    stable_sort(a,a+n,[](pair<double,double> a,pair<double,double> b){return a.second<b.second||(a.second==b.second&&a.first<b.first);});
    for(int i=1;i<n;i++) mindis=min(mindis,dist(a[i],a[i-1]));
    cout<<fixed<<setprecision(2)<<mindis<<'\n';
    delete[] a;
    return 0;
}//分析一下时空复杂度

时间复杂度分析：

对 n 个点进行稳定排序，时间复杂度为 O(nlogn)。
计算相邻点之间的距离，需要遍历 n-1 次，每次计算距离的时间复杂度为 O(1)，总时间复杂度为 O(n)。
总时间复杂度为 O(nlogn)。

空间复杂度分析：

创建了一个大小为 n 的 pair 数组 a，空间复杂度为 O(n)。
其他变量的空间复杂度为 O(1)。
总空间复杂度为 O(n)。

综上所述，该程序的时间复杂度为 O(nlogn)，空间复杂度为 O(n)。