QuickHull use Divide and Conquer But need Help !!!


  • 0
    D

    Use QuickHull for this question, but i cant remove duplicates when one point on the edge, so i use set, but anyone can tell me how to solve this without set?

    /**
     * Definition for a point.
     * struct Point {
     *     int x;
     *     int y;
     *     Point() : x(0), y(0) {}
     *     Point(int a, int b) : x(a), y(b) {}
     * };
     */
    class Solution {
    public:
        struct comp {
            bool operator()(struct Point a, struct Point  b) {
        
                if(a.x == b.x && a.y == b.y) {
                    return false;  
                } else {
                    if(a.x != b.x) {
                        return a.x < b.x; 
                    } else {
                        return a.y < b.y;     
                    }
                }
            }
        
        };
        vector<Point> outerTrees(vector<Point>& points) {
            sort(points.begin(), points.end(), cmp);
            Point a = points[0];
            Point b = points[points.size() - 1];
            vector<Point> upper = quickHull(points, a, b);
            vector<Point> lower = quickHull(points, b, a);
            upper.insert(upper.end(), lower.begin() + 1, lower.end() - 1);
            set<Point, comp> set;
            for (Point p : upper) set.insert(p);
            vector<Point> res(set.begin(), set.end());
            return res;
        }
        
        int cross(Point a, Point b, Point c) {
            return (a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y);
        }
        
        static bool cmp(Point a, Point b) {
            if (a.x == b.x && a.y == b.y) return false;
            return a.x < b. x || (a.x == b.x && a.y < b.y);
        }
        
        
        
        bool inLine(Point a, Point b, Point c) {
            if (cross(b, c, a) != 0) return false;
            if (c.x == a.x && c.y == a.y) return false;
            if (c.x == b.x && c.y == b.y) return false;
            if (c.x < min(b.x, a.x) || c.x > max(a.x, b.x)) return false;
            if (c.y < min(a.y, b.y) || c.y > max(a.y, b.y)) return false;
            return true;
        }
        
        vector<Point> quickHull(vector<Point> points, Point a, Point b) {
            vector<Point> res;
            int n = points.size();
            int maxx = INT_MIN;
            int id = -1;
            
            for (int i = 0; i < points.size(); i++) {
                int tmp = cross(b, points[i], a);
                if (tmp > 0) {
                    if (tmp > maxx) {
                        maxx = tmp;
                        id = i;
                    }
                }
            }
            
            if (id == -1) {
                res.push_back(a);
                for (int i = 0; i < points.size(); i++) {
                    if(inLine(a, b, points[i])) {
                        res.push_back(points[i]);
                    }
                }
                res.push_back(b);
            } else {
                Point c = points[id];
                vector<Point> lPoints;
                vector<Point> rPoints;
                
                for (int i = 0; i < points.size(); i++) {
                    if (cross(c, points[i], a) >= 0) lPoints.push_back(points[i]);
                    if (cross(b, points[i], c) >= 0) rPoints.push_back(points[i]);
                }
                
                vector<Point> left = quickHull(lPoints, a, c);
                vector<Point> right = quickHull(rPoints, c, b);
    
                res.insert(res.end(), left.begin(), left.end());
                res.insert(res.end(), right.begin() + 1, right.end());
            }
            return res;
        }
        
    };
    

Log in to reply
 

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