# C++ 36ms Gift wrapping algorithm

• ``````class Solution {
public:
vector<Point> outerTrees(vector<Point>& points) {
if (points.size() <= 3) return points;
vector<Point> res;
res.push_back(left_most(points));
Point pre = res[0], next;
while (1) {
next = pre;
for (auto & p : points) {
if (p.x == pre.x && p.y == pre.y) continue;
double cur = direction(pre, p, next);
if (cur == 0) {
if (next.x == pre.x && next.y == pre.y) next = p;
else if (inbetween(pre, p, next) || (visited(next, res) && next.x != res[0].x && next.y != res[0].y)) next = p;
}
else if (cur > 0) next = p;
}
if (visited(next, res)) return res;
res.push_back(next);
pre = next;
}
}
private:
Point left_most (vector<Point>& points) {
Point res;
int l_m = INT_MAX;
for (auto & p : points) {
if (p.x < l_m) {
l_m = p.x;
res = p;
}
}
return res;
}
bool visited(Point& l, vector<Point>& res) {
for (auto & p : res) {
if (p.x == l.x && p.y == l.y) return true;
}
return false;
}
double direction(Point & a, Point & b, Point & c) {
Point ab (b.x - a.x, b.y - a.y);
Point bc (c.x - b.x, c.y - b.y);
return ab.x * bc.y - ab.y * bc.x;
}
bool inbetween(Point& a, Point & b, Point & c) {
return (b.x >= a.x && b.x <= c.x || b.x >= c.x && b.x <= a.x) && (b.y >= a.y && b.y <= c.y || b.y >= c.y && b.y <= a.y);
}
};
``````

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