尋找最近點對 程式設計之美2.11

2016年搜狗筆試出現微軟程式設計之美2.11尋找最近點對題目。程式設計之美上面已經說的很清楚了，使用蠻力法時間複雜度為O（n*n），使用分治遞歸時間複雜度為O（n*log n）。以下是代碼實作：

#include<vector>

#include<iostream>

#include<utility>

#include<regex>

using namespace std;

typedef tuple<double, double,int> dpoint;         //x,y,inoutIndex

typedef tuple<double, dpoint, dpoint>answerType;//distance,point1,point2

void inputPointData(vector<dpoint> &inArray)    //input

{

    int N;

    dpoint buf;

    cin >> N;

    inArray.reserve(N);

    while (N--)

    {

        cin >> get<0>(buf) >> get<1>(buf);

        get<2>(buf) = N;

        inArray.push_back(buf);

    }

}

inline answerType get2PointDistance(dpoint &p1, dpoint &p2)

{

    return make_tuple(sqrt((get<0>(p1) - get<0>(p2))*(get<0>(p1) - get<0>(p2))

        + (get<1>(p1) - get<1>(p2))*(get<1>(p1) - get<1>(p2)))

        , p1, p2);

}

answerType GetMinDistance(vector<dpoint> &inArray, int minIndex, int maxIndex)

{

    if (maxIndex - minIndex == 1)

        return get2PointDistance(inArray[minIndex], inArray[maxIndex]);

    else    if (maxIndex - minIndex == 2)

    {

        answerType buf[3];

        buf[0] = get2PointDistance(inArray[minIndex], inArray[maxIndex]);

        buf[1] =get2PointDistance(inArray[minIndex], inArray[maxIndex-1]);

        buf[2] = get2PointDistance(inArray[minIndex+1], inArray[maxIndex]);    

        if (get<0>(buf[0]) < get<0>(buf[1]))

        {

            if (get<0>(buf[0]) < get<0>(buf[2])) return buf[0];

        }

         else if (get<0>(buf[1])< get<0>(buf[2])) return buf[1];

         return buf[2];

    }

    else if (maxIndex <=minIndex)

        return make_tuple(numeric_limits<double>::max(), inArray[minIndex], inArray[maxIndex]);

    int halfIndex = (minIndex + maxIndex) / 2;

    auto lowAns = GetMinDistance(inArray, minIndex, halfIndex);

    auto highAns = GetMinDistance(inArray, halfIndex + 1, maxIndex);

    auto minDis = get<0>(lowAns) < get<0>(highAns) ? lowAns : highAns;

    int bufIndexLow = halfIndex - 1, bufIndexHigh = halfIndex+1;

    while ( bufIndexLow >= 0&&(get<0>(inArray[bufIndexLow]) >= get<0>(minDis) +get<0>(inArray[halfIndex])))--bufIndexLow;

    while (bufIndexHigh<inArray.size()&&get<0>(inArray[bufIndexHigh]) <= get<0>(minDis) +get<0>(inArray[halfIndex]))++bufIndexHigh;

    if (bufIndexHigh - bufIndexLow + 2>0)

    {

        auto  thisAns = GetMinDistance(inArray, bufIndexLow + 1, bufIndexHigh - 1);

        return get<0>(minDis) < get<0>(thisAns) ? minDis : thisAns;

    }

    else return minDis;

}

//分治

int main()

{

    vector<dpoint> pointArray;

    inputPointData(pointArray); //input

    sort(pointArray.begin(), pointArray.end(), [](dpoint &d1, dpoint &d2){ return get<0>(d1) < get<0>(d2) ? true : false; }); //sort by x

    auto answer=GetMinDistance(pointArray, 0, pointArray.size()-1);

    auto p1 = get<1>(answer);

    auto p2 = get<2>(answer);

    if (get<2>(p1)<get<2>(p2))

        cout << get<2>(p1)<<' '<<get<2>(p2);

    else

        cout << get<2>(p2) << ' ' << get<2>(p1);

    return 0;

}