点击打开题目链接
题目大意：给出二维平面上的n个点，求出其中最近的两个点的距离的一半。
解析：这道题首先想的是暴力枚举，然而n的范围是【0，100000】，使用暴力的话一定会超时的。
然后想到分治法：将n个点按照x坐标排序，并将其分为左右两部分，分别求出其最小距离并合并。要注意，因为将所有点分成两部分了，所以没有考虑其中一点在左一点在右的情况。假设左右两部分的最短距离为d，则只要考虑【mid-d,mid+d】之间的点就可以了。在求此区间的最小值时，可以线将此区域的点按y坐标排序，分别比较（1，2）、（1，3）、……（1，m）(m<1+d)……、（2，3）、（2、4）、……、（2，m）(m-2<d)…….。
ps：开始用cin、cout输入输出，一直超时，然后用scanf、printf就不超时了。
（代码注释写的比较清楚）下面是AC了的代码：
#include <iostream> #include <cmath> #include <algorithm> #include <iomanip> #include <cstdio> using namespace std; //表示每个点的结构体 struct node { double x,y;//(x,y)表示点的坐标 int key;//点的编号 }; node ar[100005];//每个点的初始情况 node br[100005];//生成的d*2d矩形区域内的每个点的初始情况 int a,b;//表示距离最近的两个点的编号 //按x坐标比较两个点的大小 bool cmpx(node a,node b) { return a.x<b.x; } //按y坐标比较两个点的大小 bool cmpy(node a,node b) { return a.y<b.y; } //求两点之间的距离 double dis(node a,node b) { return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2)); } //用分治法求最短距离 double dac(int s,int e)//所求区间的左右端点 { //递归终止条件:区间内只有一个点 if(s==e) return 0x3f3f3f3f; int mid=(s+e)/2,tail=0;//区间终点、矩形带中点的个数 double d=min(dac(s,mid),dac(mid+1,e));//分别求左右两边的最短距离 //在d*2d矩形内可能有更小的距离 //寻找左边矩形中的点 for(int i=mid;i>=s&&ar[mid].x-ar[i].x<d;i--) br[tail++]=ar[i]; //寻找右边矩形中的点 for(int i=mid+1;i<e&&ar[i].x-ar[mid].x<d;i++) br[tail++]=ar[i]; //对矩形内的点按y坐标排序 sort(br,br+tail,cmpy); //计算矩形内任意左右两点的距离 for(int i=0;i<tail;i++) { for(int j=i+1;j<tail&&br[j].y-br[i].y<d;j++) { //找到更小距离则更新结果 if(d>dis(br[i],br[j])) { a=min(br[i].key,br[j].key); b=max(br[i].key,br[j].key); d=dis(br[i],br[j]); } } } return d; } int main() { int n; while(cin>>n&&n)//当前组输入点的个数为n { for(int i=0;i<n;i++)//输入n个点 { scanf("%lf%lf",&ar[i].x,&ar[i].y); ar[i].key=i+1;//当前点的编号 } //按x坐标对所有点排序 sort(ar,ar+n,cmpx); //调用分治函数求最小值 printf("%.2f\n",dac(0,n)/2); } return 0; }