【洛谷1429】平面最近点对

观察性质的能力还是欠缺啊pxp 原题： 给定平面上n个点，找出其中的一对点的距离，使得在这n个点的所有点对中，该距离为所有点对中最小的 $ 2\leq n\leq 200000 $ 这题其实可以kdtree做 但是数据结构太无脑了！ 这个时候当然是选择优美的分治啦~ 因为这道题不是曼哈顿距离，而且点的坐标也不是整数，所以不能再用三维偏序那一套理论 想这个题的时候把思维从cdq分治里边拉出来还是费了一番功夫 因为这题我没有自己想出来，所以不再做思路引导，直接说明做法和正确性 首先是做法 直接看做法不容易理解，建议结合正确性证明观看 开始分治前先以横坐标为第一优先级排序 这道题使用的是后序分治，先递归分治两边的区间，获得两边区间里的最优值d （两个区间显然要对半分 然后将右边区间中所有满足横坐标和中点横坐标之差小于d的点全部按下标递增的顺序收录到一个队列里 现在按下标递增的顺序扫描左边的点，每遇到一个满足横坐标和中点横坐标之差小于d的点，首先从队尾逐渐将不满足纵坐标和当前点纵坐标之差小于d的点出队，再从队尾向后扫描所有点，直到到达队头或队中点的纵坐标和当前点之差大于d 对于每一个扫描到的队中的点，计算和当前点的距离并更新答案 最后以归并排序的形式把当前区间以纵坐标为第一优先级排序 现在说明正确性 开始对横坐标的排序只是快速取到区间中间点的横坐标以确保复杂度 两边递归后的操作实际上是对于每个横坐标和中线距离差小于d的点，把以这个点为左边中点的正方形中的所有点拿出来，并统计答案 因为如果两个点的横坐标差大于d，显然一定不会是最优解，纵坐标同理 d是递归得到的，可以放心交给递归而不用管它 最后的归并排序保证区间合并后y是单调的，这样就可以通过队列的方式快速选出正方形中的点 现在证明复杂度 由鸽巢原理易得正方形中的点不会超过6个 （想象一下往一个边长为2d的正方形里塞半径是d的球，塞不了几个 那么每个左边的点统计答案的时间是一个很小的常数，可以忽略 对于队列操作，每个点最多进一次队，出一次队，复杂度为$ O(n) $ 归并排序也是$ O(n) $ 那么令$ T(n) $为算法复杂度，满足$ T(n)=2T(\frac{n}{2})+O(n) $ 由主定理可得最终复杂度为$ \Theta (nlogn) $ （题解写的有点奇怪，还是需要理解清楚，思路再从头考虑一个 这个做法的核心，就是应用了两边分治完后y单调的性质，以及想到在中线两边横坐标距离小于d的范围内选点这样一个结论 d也是两边分治的到的，所以分治时注意分治得到的性质真的是很重要呢~ 有一些注意事项 注意边界（r=l+1）的时候不要忘了处理y的顺序 区间中点是会变的（两边递归的时候对y进行了排序），所以要先记录一下中点横坐标 代码： ```cpp #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; const double oo=1e9; int rd(){int z=0,mk=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')mk=-1; ch=getchar();} while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0'; ch=getchar();} return z*mk; } struct nds{double x,y;}a[210000]; inline double sqr(double x){ return x*x;} inline double dstc(nds x,nds y){ return sqrt(sqr(x.x-y.x)+sqr(x.y-y.y));} int n; nds q[210000]; int hd=0,tl=1; int bnrsch(double x,int l,int r){ int md; while(l+1<r) md=(l+r)>>1,(q[md].y>x ? l : r)=md; return q[l].y>x ? l : r; } double dac(int l,int r){ if(l==r) return oo; if(r==l+1){ if(a[l].y>a[r].y) swap(a[l],a[r]); //注意边界的时候处理y的排序 return dstc(a[l],a[r]); } int md=(l+r)>>1; double mdx=a[md].x; //注意a[md]会变！！！！！！ double d=min(dac(l,md),dac(md+1,r)); double bwl=d; hd=0,tl=1; for(int i=md+1;i<=r;++i) //if(abs(a[i].x-a[md].x)<d) if(abs(a[i].x-mdx)<d) q[++hd]=a[i]; for(int i=l;i<=md;++i) if(abs(a[i].x-mdx)<d){ while(tl<=hd && a[i].y-q[tl].y>d) ++tl; for(int j=tl;j<=hd && abs(a[i].y-q[j].y)<d;++j) bwl=min(bwl,dstc(a[i],q[j])); } int hd1=l,hd2=md+1; for(int i=l;i<=r;++i){ if(hd2<=r && (hd1>md || a[hd2].y<a[hd1].y)) q[i]=a[hd2++]; //注意不要忘了hd2<=r else q[i]=a[hd1++]; } for(int i=l;i<=r;++i) a[i]=q[i]; return bwl; } bool cmp(nds x,nds y){ return x.x==y.x ? x.y<y.y : x.x<y.x;} //给初始数组的所有维度都排个序是好习惯 int main(){//freopen("ddd.in","r",stdin); freopen("ddd.out","w",stdout); cin>>n; for(int i=1;i<=n;++i) scanf("%lf %lf",&a[i].x,&a[i].y); sort(a+1,a+n+1,cmp); printf("%.4lf\n",dac(1,n)); return 0; } ```