算法：极点问题

题目：

平面上有一些点，每个点的坐标可用(x,y)表示。请找出所有的极点。
对于平面上的两个点:A(x1,y1) 和 B(x2,y2)，如果x1>x2,且y1>y2,则点A支配点B。极点是不被其他点支配的点。

思路：

暴力法的时间复杂度是O(n²)。本题利用分治法可以使时间复杂度降到NlogN。具体步骤：

1. 首先对数组排序，使所有点在x轴上从小到大排列
2. 把数组分为左右两部分，分别求极点
3. 对2步骤的两个结果合并，不过要先过滤左边部分有可能被右边极点支配的点。

代码：

#include <vector>
using namespace std;
class MaximumPoint {
    static bool compareTwoPoint(vector<int> point1, vector<int> point2) {
        return point1[0] < point2[0];
    }
public:
    vector<vector<int>> findMaximumPoint(vector<vector<int>>& arr, int left, int right) {
        if (left > right) {
            return {{}};
        }
        if (left == right) {
            return {arr[left]};
        }
        sort(arr.begin(), arr.begin()+(right - left), compareTwoPoint);
        int mid = left + (right - left)/2;
        vector<vector<int>> leftR = findMaximumPoint(arr,left,mid);
        vector<vector<int>> rightR = findMaximumPoint(arr, mid + 1, right);
        //找出rightR里 x最小的极点
        vector<int> minPoint = rightR.front();
        for(int i = 1;i < rightR.size();i++) {
            if (minPoint[0] > rightR[i][0]) {
                minPoint = rightR[i];
            }
        }
        //如果leftR里，有点y < minPoin[1]，则排除
        for(int i = 0;i < leftR.size();i++) {
            if (leftR[i][1] < minPoint[1]) {
                leftR.erase(leftR.begin()+i);
                i--;
            }
        }
        
        //合并 leftR和rightR
        rightR.insert(rightR.end(), leftR.begin(), leftR.end());
        return rightR;
    }
};