题目链接:https://www.acwing.com/problem/content/121/
经典问题,平面最近点对,使用分治来解决
把所有点按横坐标排序,分治求解距离
合并时将两边的最近点对距离也比较一下
属于不同集合的点比较距离时判断一下即可
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn = 200010;
const double INF = 2 << 28;
int T, n, tot;
struct Point{
double x, y;
}p[maxn], tmp[maxn];
bool cmp(Point a, Point b){
return a.x < b.x;
}
double calc(Point a, Point b){
double X = (a.x - b.x);
double Y = (a.y - b.y);
return sqrt(X * X + Y * Y);
}
double Merge(int L, int R){
double dis = INF;
if(L == R){
return dis;
}
if(L + 1 == R){
return calc(p[L], p[R]);
}
int mid = (L + R) >> 1;
double d1 = Merge(L, mid);
double d2 = Merge(mid + 1, R);
dis = min(d1, d2);
int cnt = 0;
for(int i=L; i <= R; ++i){
if(fabs(p[i].x - p[mid].x) < dis){
tmp[++cnt] = p[i];
}
}
sort(tmp + 1, tmp + 1 + cnt, cmp);
for(int i = 1;i <= cnt; ++i){
for(int j = 1;j < i; ++j){
dis = min(dis, calc(tmp[i], tmp[j]));
}
}
return dis;
}
ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*f; }
int main(){
n = read(); tot = 0;
for(int i=1;i<=n;++i){
++tot;
scanf("%lf %lf",&p[tot].x, &p[tot].y);
}
sort(p + 1, p + 1 + tot, cmp);
printf("%.4lf\n",Merge(1,tot));
return 0;
}