分治法求近期点对

递归将点不断分成小组。计算最短距离。此时的最短距离不过两点都属两块的某一块（这里的切割点是mid点）。

还须要考虑两点分属两块的情况。

这时对于选点则把范围缩小到了以mid为中心。

再将距离mid点x轴2*mindist范围点考虑在内。在这些点中，再取mid点，留下那些

y的距离不大于middist 的点进行距离计算。

PS：刚開始min函数写错了。写成了max，一直tle.使用max则会导致选取的点越来越多。TLE则就不奇怪了。

对于使用递归方法实现分治。事实上质使用了小范围内得到的结果会缩小总体范围内的搜索空间。递归函数要有范围參数噢。

递归的直观理解能够是1 2 3 等简单情况完后得到的结果返回，组拼全局解。

#include <iostream>

#include <math.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <algorithm>

using namespace std;

const int maxn=100005;

int n;

struct P

{

    double x,y;

}p[maxn],ans[maxn];

double min(double a,double b){return a<b?a:b;}

bool cmpx(struct P a,struct P b){return a.x<b.x;}

bool cmpy(struct P a,struct P b){return a.y<b.y;}

double dist(struct P a,struct P b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}

double solve(int l,int r)

{

    if(l+1==r)

        return (dist(p[l],p[r]));

        else if(l+2==r)

            return min(dist(p[l],p[l+1]),min(dist(p[l+1],p[r]),dist(p[r],p[l])) );

    int mid=(l+r)>>1;

    double res=min(solve(l,mid),solve(mid+1,r));//这里避免了==mid 的情况

    int cnt=0,i,j;

    for(i=l;i<=r;i++)

    {

        if(fabs(p[i].x-p[mid].x)<=res)

            ans[cnt++]=p[i];

    }

    sort(ans,ans+cnt,cmpy);

    for( i=0;i<cnt;i++)

        for( j=i+1;j<cnt;j++)

    {

        if(ans[j].y-ans[i].y>=res) break;

        res=min(res,dist(ans[i],ans[j]));

    }

    return res;

}

int main()

{

    while(scanf("%d",&n),n)

    {

        int i;

        for(i=0;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);//输入点

        sort(p,p+n,cmpx);//按x排序

        double res=solve(0,n-1);

        printf("%.2lf\n",res/2);

    }

    return 0;

}