C++ 36ms Gift wrapping algorithm


  • 0
    C
    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);
        }
    };
    

Log in to reply
 

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