题解 P1429 【平面最近点对（加强版）】

这是一道很难很难很难很难很难的题 你永远不会想到用二分吧？ O(∩\_∩)O米兔 所以来看看怎么用二分的吧 首先嘛，可以肯定的是，每两个去算距离O(n^2)的复杂度肯定会超时的 所以二分是个不错的选择，可以将时间降到O(nlog2n)（二分log2n然后比较各个点的距离与答案约是n） 于是——怎么分 ✔将各个点（结构体）按x的从小到大排序 ✔首先运用二分思想将点集合分到最后只剩两个点的时候 ✔然后用这两点之间的距离更新答案（答案初始化为无限大） ✔然后我们要找到二分的具体实现方案——每次分到一些点时，找到这些点标号的中间（因为点都排好序了，所以其实也就是找到x轴上一条分界线），将整个点的集合大致均分为两个部分 ✔在分界线的右侧，将与分界线的距离小于ans的点纳入到一个辅助结构体里面 ✔在分界线的左侧，不断枚举点，枚举到离分界线小于ans的点时，与辅助结构体中的点**挨个**（等会有解释）判断其距离有没有小于ans，更新ans 注意下用double**别掉了精度**，然后格式化输出就好了 然后我的代码中，为了避免超时，还是很努力地自己写了个实数的输入优化没想到也过了 解释下这个“挨个” 有些题解中在每次更新完ans后都将这些点按y轴从小到大排了序，然而我并不知道这有什么用，照着题解打一遍WA了一个点，然后。。调试一番后感觉真的没什么卵用，去掉了（注释部分）再在源代码上稍加修改，就过了 ……………………………… …………………………………… ……………………………… …………………………………… ………………………………………… ……………………………… 请教大佬中（询问这个排序有什么用） 嗯，这个排完序后当扫到一个点与该点距离大于ans时，就可以不再扫了 但是，，难道排序不要时间吗。。。所以可能也许大概排完序后有那么一丢丢优化/笑哭/ ```cpp #include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> using namespace std; struct dian{ double x,y; }a[200001],b[200001]; int n; int cmpx(const dian&a,const dian&b) { if(a.x<b.x) return 1; if(a.x>b.x) return 0; if(a.y<b.y) return 1; return 0; } double read() { char ch=getchar(); while(ch!='.'&&(ch>'9'||ch<'0')) ch=getchar(); int h=0,t=1,b=0; while(ch!='.'&&ch<='9'&&ch>='0') { h=h*10+ch-48; ch=getchar(); } if(ch=='.') { ch=getchar(); while(ch<='9'&&ch>='0') { b=b*10+ch-48; ch=getchar(); t*=10; } } return h+(b*1.000000000)/t; } double mini(double a,double b) { return a>b?b:a; } double ans=1000000000; void merge(int l,int r) { if(l==r) return; int mid=(l+r)/2;//找到中间位置的点 merge(l,mid); merge(mid+1,r);//递归调用 //memset(b,0,sizeof(b)); int line=a[mid].x;//分界线 int p=1;//指向b的首位（b数组按照x轴顺序来的） int t=0;//指向b的存储的位置 for(int i=mid+1;i<=r;i++)//枚举分界线右边的点 { if(a[i].x-line<ans) b[++t]=a[i];//如果该点与分界线的距离小于答案的话，将此点存入b中 } for(int i=l;i<=mid;i++) { if(line-a[i].x>=ans) continue;//如果该点与分界线的距离大于答案，继续找 //while(p<=t&&a[i].y-b[p].y>=ans)//要求在b中找到一个p // p++;//使得a[i]的y轴坐标-b[p]的值要小于答案 for(int j=p;j<=t&&abs(b[j].y-a[i].y)<ans;j++)//不断地枚举b中剩下的点 ans=mini(ans,sqrt((a[i].x-b[j].x)*(a[i].x-b[j].x)+(a[i].y-b[j].y)*(a[i].y-b[j].y)));//然后更新答案 } /*for(int i=l,p1=l,p2=mid+1;i<=r;i++) if(p1<=mid&&(p2>r||a[p1].y<a[p2].y)) b[i]=a[p1++]; else b[i]=a[p2++]; for(int i=l;i<=r;i++) a[i]=b[i];//按纵坐标从小到大排序 */ } int main() { n=read(); for(int i=1;i<=n;i++) { a[i].x=read(); a[i].y=read(); } sort(a+1,a+n+1,cmpx);//以X为关键字排序 merge(1,n);//将1到n去查找 printf("%0.4lf",ans); return 0; } ```