为最近对问题的一维版本设计一个直接基于分治技术的算法,并确定它的时间复杂度。假设输入的点是以升序保存在数组A中。（最近点对问题定义：已知上m个点的集合，找出对接近的一对点。）

#include <iostream>
#include <limits.h>

using namespace std;

int closestPointPair(int * arr, int p, int q)//分治计算最近距离
{
    if(p==q)
    {
        return INT_MAX;
    }
    else if(p<q)
    {
        int m=(p+q)/2;
        int Ldis = closestPointPair(arr, p, m);
        int Rdis = closestPointPair(arr, m+1, q);
        int dis = arr[m+1]-arr[m];

        int Min = Ldis<Rdis?Ldis:Rdis;
        Min = Min<dis?Min:dis;
        return Min;
    }
}

struct pointPair
{
    int x;
    int y;
};

struct pointPair closestPointpair(int *arr, int p, int q)//分治计算最近距离的点对
{
    if(p==q)
    {
        struct pointPair pointpair = {INT_MIN,INT_MAX};
        return pointpair;
    }
    else if(q-p==1)
    {
        struct pointPair pointpair = {arr[p], arr[q]};
        return pointpair;
    }
    else
    {
        int m = (p+q)/2;
        struct pointPair Lpointpair = closestPointpair(arr, p, m);
        struct pointPair Rpointpair = closestPointpair(arr, m+1, q);
        struct pointPair Cpointpair = {arr[m], arr[m+1]};
        struct pointPair cpp = (Lpointpair.y-Lpointpair.x) < (Rpointpair.y-Rpointpair.x)?Lpointpair:Rpointpair;
        cpp = (cpp.y-cpp.x) < (Cpointpair.y-Cpointpair.x)?cpp:Cpointpair;
        return cpp;
    }
};

int main()
{
    int arr[8]={1,4,6,8,10,11,15,17};
    cout<<closestPointPair(&arr[0], 0, 7)<<endl;

    struct pointPair pp = closestPointpair(&arr[0], 0, 7);
    cout<<pp.x <<","<<pp.y<<endl;
    return 0;
}