分治例题

个人理解：先排序，然后将\(n\)个点均分成左右两部分，分别求出左边点之间的最近距离\(d1\),和右边点的最近距离\(d2\),取\(d=min(d1,d2)\)。然后考虑最近点队的两个点分属于两边的情况，肯定只可能是很靠近中间线的那几个点（题解里证明不超过六个）。加个剪枝优化，横坐标距离\(s[mid].x\)（中点线）大于\(d\)的肯定不行。将所有据中点线距离不超过\(d\)的点取出，按\(y\) 值排个序，对于每一个点，只需要考虑它后面（下面）的\(y\) 值据它不超过 \(d\) 的点，超过就可以\(break\)(因为排好序了嘛)。

代码时间：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int N = 1000005;const int inf = 2<<20;int n,temp[N];struct point{    double x,y;}s[N];bool cmp(point a,point b){    if(a.x==b.x) return a.y
         
          >1; double d1=merge(left,mid); double d2=merge(mid+1,right); d=min(d1,d2); int k=0; for(int i=left;i<=right;i++) if(fabs(s[mid].x-s[i].x)<=d) temp[++k]=i; sort(temp+1,temp+k+1,cmps); for(int i=1;i<=k;i++) for(int j=i+1;j<=k&&s[temp[j]].y-s[temp[i]].y
          
           d3) d=d3; } return d;}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lf%lf",&s[i].x,&s[i].y); sort(s+1,s+n+1,cmp); printf("%.4lf\n",merge(1,n)); return 0;}