针对网上题解抄来抄去我就不吐槽了。
最近点对，经典问题，分治法。另外解题方法就不累述了，关键是要理解到在二分线那儿选择一个2d*d的矩形区域，将里面所有点再拿出来枚举一遍。
另外此代码来自挑战程设这本书。
//hdu 1007 #include<iostream> #include<cstdio> #include<vector> #include<algorithm> #include<cmath> using namespace std; #define inf 999999999999.0; typedef pair<double,double> P; P p[100000+9]; int cmp(P a,P b) { return a.second<b.second; } double close_pair(P *a,int n) { if(n<=1) return inf; int m=n/2; double x=a[m].first; double d=min(close_pair(a,m),close_pair(a+m,n-m)); inplace_merge(a,a+m,a+n,cmp); vector<P> b;//最妙的就是这里了，不用先把点全部装入vector中 for(int i=0;i<n;i++) { if(fabs(a[i].first-x)>=d) continue; for(int j=0;j<b.size();j++) { double dx=a[i].first-b[b.size()-j-1].first; double dy=a[i].second-b[b.size()-j-1].second; if(dy>=d) break; d=min(d,sqrt(dx*dx+dy*dy)); } b.push_back(a[i]); } return d; } int main() { double x,y;int n; while(scanf("%d",&n)!=EOF) { if(n==0) break; for(int i=0;i<n;i++) scanf("%lf%lf",&x,&y),p[i]=make_pair(x,y); sort(p,p+n); printf("%.2f\n",close_pair(p,n)*0.5); } }
转载于:https://www.cnblogs.com/Airplus/p/3912646.html
