平面上的最接近点对

题目

给定平面上 n 个点，找出其中的一对点的距离，使得在这 n 个点的所有点对中，该距离为所有点对中最小的。

分治，区间l, r的值是左区间和右区间和左右两个区间的距离最小。

求解复杂度nlogn

左右两区间可以仅查找l到r中x轴位置距离小于左区间和右区间求解得到的最小值，进行优化。可能会出现暴力的情况，但是已经被证明总的复杂度可以在nlogn内解决。

代码

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define nrep(i,a,b) for(int i=a;i>=b;i--)
#define all(a) a.begin(),a.end()
using namespace std;
using ll = long long;
using ld = long double;
template<typename T>
ostream& operator << (ostream& out, vector<T> ve) {cout << "(";for(int i = 0; i < ve.size(); i++) {cout << ve[i] << ",)"[i == ve.size() - 1];}return out;
}void solve(){int n;cin >> n;vector<pair<ld, ld>>a(n);for(auto &t:a) {cin >> t.first >> t.second;}auto dis = [&a](int x, int y) -> ld {ld ans = pow(a[x].first-a[y].first,2) + pow(a[x].second - a[y].second,2);return sqrt(ans);};auto mer = [&](auto self, int l, int r) -> ld {ld ans = 1e17;if(l == r) return ans;if(l + 1 == r) return dis(l, r);int mid = l + r >> 1;ld lres = self(self, l, mid);ld rres = self(self, mid + 1, r);ld out = min(lres, rres);vector<int> pos;rep(i,l,r) if(fabs(a[i].first - a[mid].first) < out) {pos.push_back(i);}sort(pos.begin(),pos.end(),[&](int u, int v) {return a[u].second < a[v].second;});for(int i = 0; i < pos.size(); i++) {for(int j = i + 1; j < pos.size()&& a[pos[j]].second - a[pos[i]].second < out; j++){out = min(out, dis(pos[i], pos[j]));}}return out;};sort(a.begin(),a.end(),[](auto l,auto r) {return l.first == l.second ? l.second < r.second : l.first < r.first;});cout << fixed << setprecision(4) << mer(mer, 0, n-1);
}
signed main() {ios::sync_with_stdio(false);int t=1;//cin >> t;while(t--){solve();}
}