# C++ O(nlogn) Solution

• ``````    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;
}
``````

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