最近点对问题

今天我与一道题较上了劲，这题名叫最近点对，该题用分治法解答。废话不多说，贴上题目（来自cugboj）：

题目主要解答步骤为：
1、将输入的数优先x升序其次y升序的方法排序；通过sort、qsort或同等效率的排序算法解决；
2、写出求两点距离的函数dis(…….)。（参数省略，以下也省略）
3、因为对于任意区间【l，r】我们可以分为两部分，进行三次讨论。前两次讨论即【l，mid-1】区间内的最近距离，【mid，r】区间内的最近距离，然后去上述最近距离的最小值d。这两个区间可以通过递归调用解决，边界条件见步骤五。
4、第三次讨论是：对位于【mid-d，mid+d】区间内的点对（该区间内的点对有可能距离小于d）进行距离讨论，注意要先按y坐标排序，for循环遍历每个点，循环过程中只需要讨论每个点上下距离为d的点对（即竖直距离大于d时continue）（情况复杂，详见代码），最后视情况更新d。
5、递归结束条件为区间内只有两点或一点，当区间内只有一点时，返回MAXN（自定义的无限大），当区间内有两点时，返回值为这两地点的距离。
贴上ac代码：

#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 2147483647
#define DOUM 1e300
class adre
{
    public:
        double x,y;
};
adre adr[100005];
int temp[100005];
int cmp(adre a,adre b)
{
    if(a.x!=b.x) return a.x<b.x;
    else return a.y<b.y;
}
int cmpy(int a,int b)
{
    return adr[a].y<adr[b].y;
}
double dis(adre a,adre b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double closestpoint(int left,int right)
{
    double d1,d;
    int mid=(left+right)>>1;
    if(left+1==right) return dis(adr[left],adr[right]);
    if(left+2==right) return min(dis(adr[left],adr[right]),min(dis(adr[left],adr[left+1]),dis(adr[left+1],adr[right])));
    d=min(closestpoint(left,mid),closestpoint(mid+1,right));
    int i,j,k=0;
    for(i=left;i<=right;i++)
    {
        if(fabs(adr[i].x-adr[mid].x)<=d) temp[k++]=i;
    }
    sort(temp,temp+k,cmpy);
    for(i=0;i<k;i++)
    {
        for(j=i+1;j<k;j++)
        {
            if(adr[temp[j]].y-adr[temp[i]].y>=d) break;
            d1=dis(adr[temp[i]],adr[temp[j]]);
            if(d1<d) d=d1;
        }
    }
    return d;
}
int main()
{
    int n,i,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++) scanf("%lf %lf",&adr[i].x,&adr[i].y);
        sort(adr,adr+n,cmp);
        printf("%.2f\n",closestpoint(0,n-1));
    }
    return 0;
}