假设当前区间为[l,r] 中间点为mid
那么最近点对 要么在[1,l]中，要么在[l+1,r]中，要么两边各有一个
我们递归处理出左区间的 最近点对距离d1 右区间d2 取d=min(d1,d2)
然后有两个剪枝来处理情况3
1.按x为关键字排个序，枚举[l,r]的点，假如一个点的x与中间点的x差值已经超过了d，那肯定不满足要求，因为还要算上y
2.剪枝1还不够，当我们已经筛选出符合剪枝1的点后，把这些点又按照y为关键字排个序，同样的，假如一个点的y与当前点的x差值已经超过了d，那他之后的点都是不满足要求的，可以break掉，然后顺便统计答案
#include<bits/stdc++.h> #define N 100005 using namespace std; struct Node { double x,y; }p[N]; int n; inline bool cmp1(const Node &a,const Node &b) { if(a.x==b.x) return a.y<b.y; return a.x<b.x; } inline bool cmp2(const int &a,const int &b) { return p[a].y<p[b].y; } double dis(Node a,Node b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } int temp[N]; double solve(int l,int r) { if(l+1==r) return dis(p[l],p[r]); if(l+2==r) return min(dis(p[l],p[r]),min(dis(p[l+1],p[r]),dis(p[l],p[l+1]))); int mid=(l+r)>>1; double d=min(solve(l,mid),solve(mid+1,r)); int cnt=0; for(int i=l;i<=r;i++) { if(p[i].x>=p[mid].x-d&&p[mid].x+d>=p[i].x) temp[++cnt]=i; } sort(temp+1,temp+cnt+1,cmp2); for(int i=1;i<=cnt;i++) { for(int j=i+1;j<=cnt;j++) { if(p[temp[j]].y-p[temp[i]].y>=d) break; d=min(d,dis(p[temp[i]],p[temp[j]])); } } return d; } int main() { ios::sync_with_stdio(false); cin.tie(NULL),cout.tie(NULL); while(cin>>n&&n) { for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].y; sort(p+1,p+n+1,cmp1); cout<<fixed<<setprecision(2)<<solve(1,n)/2<<'\n'; } return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9880148.html
