分治法求解凸包问题

求解二维凸包问题，时间复杂度为O(nlogn)，即先通过点集中每个点的x值将点集划分为左右两部分，分别求解其凸包，再通过two finger方法将两个凸包合并，时间复杂度类似于合并排序，完整代码如下，包含一个测试用例，可直接运行（具体的算法讲解可看OCW 6.046J第2集）。

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>

using namespace std;

//二维点
struct point2d{
    double x;
    double y;
    point2d(double _x, double _y): x(_x), y(_y){}
    operator double(){return x;}
};

//前向声明
list<point2d> two_finger(list<point2d>& left, list<point2d>& right);

//解决convex hull问题的主要函数，利用divide and conquer
//pts中的点按照x轴从小到大排列，链表中的点按顺时针排列
list<point2d> convex_hull(vector<point2d>& pts, int l, int r){
    if(r - l + 1 <= 3)//基本情况
        return list<point2d>(pts.begin() + l, pts.begin() + r + 1);
    int mid = (l + r) / 2;
    //左侧子问题的解
    auto left = convex_hull(pts, l, mid);
    //右侧子问题的解
    auto right = convex_hull(pts, mid + 1, r);
    //合并左右两侧子问题（采用视频中提到的two finger方法）
    return two_finger(left, right);
}


//计算p1和p2连线交于x的y
inline double y_intersect(const point2d& p1, const point2d& p2, double x){
    return p1.y + (p2.y - p1.y) / (p2.x - p1.x) * (x - p1.x);
}

//跳过end迭代器
list<point2d>::iterator mynext(list<point2d>::iterator it, list<point2d>& lst){
    ++it;
    if(it == lst.end()) ++it;
    return it;
}

//跳过end迭代器
list<point2d>::iterator myprev(list<point2d>::iterator it, list<point2d>& lst){
    --it;
    if(it == lst.end()) --it;
    return it;
}

//视频中的two finger算法
list<point2d> two_finger(list<point2d>& left, list<point2d>& right){
    //找到左侧凸包中x最大的点,即a1
    auto a1 = left.end();
    for(auto it = left.begin(); it != left.end(); ++it)
        if(a1 == left.end() || *it > *a1)
            a1 = it;
    //找到右侧凸包中x最小的点,即b1
    auto b1 = right.end();
    for(auto it = right.begin(); it != right.end(); ++it)
        if(b1 == right.end() || *it < *b1)
            b1 = it;
    //分割线对应的x
    double x = (a1->x + b1->x) / 2;
    //利用two finger找到上切线和下切线
    //上切线
    auto ai = a1;
    auto bj = b1;
    while(y_intersect(*ai, *mynext(bj, right), x) > y_intersect(*ai, *bj, x) ||
          y_intersect(*myprev(ai, left), *bj, x) > y_intersect(*ai, *bj, x)){
        if(y_intersect(*ai, *mynext(bj, right), x) > y_intersect(*ai, *bj, x))
            bj = mynext(bj, right);
        else
            ai = myprev(ai, left);
    }
    //下切线
    auto ak = a1;
    auto bm = b1;
    while(y_intersect(*ak, *myprev(bm, right), x) < y_intersect(*ak, *bm, x) ||
          y_intersect(*mynext(ak, left), *bm, x) < y_intersect(*ak, *bm, x)){
        if(y_intersect(*ak, *myprev(bm, right), x) < y_intersect(*ak, *bm, x))
            bm = myprev(bm, right);
        else
            ak = mynext(ak, left);
    }
    //按顺时针找出边界上的点
    list<point2d> rslt;
    //ai->bj
    rslt.push_back(*ai);
    //右侧(循环遍历)
    for(auto it = bj; it != bm; ++it){
        if(it == right.end()){
            it = right.begin();
            if(it == bm) break;
        }
        rslt.push_back(*it);
    }
    //bm->ak
    rslt.push_back(*bm);
    //左侧(循环遍历)
    for(auto it = ak; it != ai; ++it){
        if(it == left.end()){
            it = left.begin();
            if(it == ai) break;
        }
        rslt.push_back(*it);
    }
    return rslt;
}

void print(ostream& os, list<point2d>&& lst){
    os << "pts: ";
    for(auto pt: lst)
        os << "{" << pt.x << ", " << pt.y << "} ";
    os << endl;
}

//总的时间复杂度为O(nlogn)利用主定理很容易证明
//由于two finger算法时间复杂度为O(n)（可类比为
//merge sort中的merge过程）所以convex hull时间
//复杂度和merge sort一致，均为O(nlogn)
int main(){
    vector<point2d> test_point = {{1, 1}, {2, 2}, {3, 1.5},
                                  {4, 1.5}, {5, 2}, {6, 1},
                                  {3.5, 4}};

    //按照x对点进行排序
    sort(test_point.begin(), test_point.end());

    //求解convex hull
    print(cout, convex_hull(test_point, 0, test_point.size() - 1));
}