C++ O(nlogn) Solution


  • 1
        vector<Point> outerTrees(vector<Point>& points) {
            if(points.size() < 3) return points;
            auto cmp = [](Point& a, Point& b) -> bool {
                return a.x < b.x || (a.x == b.x && a.y < b.y);
            };
            sort(points.begin(), points.end(), cmp);
            vector<Point> stack;
            stack.push_back(points[0]);
            stack.push_back(points[1]);
            //left to right;
            for(int i = 2; i < points.size(); ++i) {
                while(stack.size() > 1) {
                    auto &t1 = stack.back();
                    auto &t2 = stack[stack.size() - 2];
                    if(isRightTurn(t2, t1, points[i])) break;
                    else stack.pop_back();
                }
                stack.push_back(points[i]);
            }
            int n = stack.size();
            if(n == points.size()) return stack; //check if linear
            stack.push_back(points[points.size() - 2]);
            //right to left;
            for(int i = points.size() - 3; i >= 0; --i) {
                while(stack.size() > n) {
                    auto &t1 = stack.back();
                    auto &t2 = stack[stack.size() - 2];
                    if(isRightTurn(t2, t1, points[i])) break;
                    else stack.pop_back();
                }
                stack.push_back(points[i]);
            }
            stack.pop_back();
            return stack;
        }
        
        bool isRightTurn(Point &a, Point &b, Point &c) {
            return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x) <= 0;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.