在做求平面内最近点对的问题时，使用两种不同的比较方法求最小距离，算法效率在100000输入规模下相差2~3倍，很费解，想向大家求助。

具体来说只有求两点距离的方法是不一样的（然而却导致了不同）：

一是先一直用平方表示距离，最后输出算开根

 if (s == e) return MAX;   //如果只有一个点返回无限大
 if (s + 1 == e) return square(ar[s], ar[e]);//如果只有两个点返回开根后的距离
 

二是每次都直接算出开根以后的距离

   if (s == e) return MAX;   //如果只有一个点返回无限大
   if (s + 1 == e) return dis(ar[s], ar[e]);//如果只有两个点返回开根后的距离

以上两种情况都是递归到底后执行，此外还有比较中间是否有最小距离时需要用到

curmin = min(curmin, square(ar[sr[i]], ar[sr[j]]));
curmin = min(curmin, dis(ar[sr[i]], ar[sr[j]]));//(当前求得的两边最小值,中间最小值）

double dis(Node a, Node b) { return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2)); }  //返回点与点之间的距离
double square(Node a, Node b) { return  pow(a.x - b.x, 2) + pow(a.y - b.y, 2); } //square()和dis()除了是否开根以外没有任何差别。

两种方法在100000规模下运行20次取平均运行时间如图1和图2所示

图1 dis方法

图2 square方法

输入使用随机数，在随机数中规模大约平均在10的4次方，显然square产生的数字要比dis大得多，每次比较的数字也大的多，比较的复杂度是O(n)的。但是用同样的类型存储数据，也都没有溢出，占位应该是相同的，而且比较是大家都要比较的，dis方法只是数比较小，何况dis每次运算是通过计算平方再开根，多了开根这一步，为什么用dis方法反而会快呢？如何理解数据规模对比较的影响呢？

源码如下：

#include
#include
#include
#include
#include
using namespace std;

double MAX = 1e10; //定义的最大距离，以在只有一个点的时返回无穷大
int a, b;   //用来记录下标，与题无关
struct Node {
    double x, y;
    int key;   //关键码，可有可无，与ab有关
};


Node ar[100005];
int sr[100005];

bool cmpx(Node a, Node b) { return a.x> 1;
    double curmin = min(shortest(s, mid), shortest(mid + 1, e));
    listlen = 0;
    for (i = mid; i >= s && ar[mid + 1].x - ar[i].x <= curmin; i--)
        sr[listlen++] = i;
    for (i = mid + 1; i <= e && ar[i].x - ar[mid].x <= curmin; i++)
        sr[listlen++] = i;
    qsort(sr, listlen, sizeof(sr[0]), listcmp);//对y进行排序
    for (i = 0; i < listlen; i++)
        for (j = i + 1; j < listlen && ar[sr[j]].y - ar[sr[i]].y <= curmin; j++)
            curmin = min(curmin, dis(ar[sr[i]], ar[sr[j]]));
    return curmin;
}
void myRun (int n) {
    time_t start, end;
    double distance;
    double sum = 0.0;
    cout << "分治法在" << n << "规模耗时结果如下：" << endl;
    for (int i = 0; i < 20; i++) {
        create(n);
        sort(ar, ar + n, cmpx);  //按x对ar排序
        start = clock();
        double distance = shortest(0, n);
        end = clock();
        //if (i == 0) cout << "分治法在"<