O(N) easy to understand c++ solution (69ms)


  • 1
    S

    x1y2-x2y1:
    U^ X V^ =
    i^ j^ k^
    x1 y1 z1
    x2 y2 z2

    = (x1y2 - y1x2)k^ (ignoring i^ and j^ components because z1 & z2 are zeros)

    • a^ means a with an arrow on top of it. Basically, it's a vector.
    • X mean cross product.

    update: bug fixed to handle new test cases by adding this line:
    if(cur == 0) continue;

    public:
        bool isConvex(vector<vector<int>>& points) {
            int n = points.size();
            if(n <= 3) return true;
            points.push_back(points[0]);
            points.push_back(points[1]);
            long cur = 0, pre = 0;
            for(int i = 2; i < n+2; ++i) {
                int x1 = points[i-1][0] - points[i-2][0];
                int y1 = points[i-1][1] - points[i-2][1];
                int x2 = points[i][0] - points[i-2][0];
                int y2 = points[i][1] - points[i-2][1];
                cur = x1*y2-x2*y1;
                if(cur == 0) continue;
                if(pre*cur < 0) return false;
                else pre = cur;
            }
            points.pop_back();
            points.pop_back();
            return true;
        }
    };

  • 1
    W

    @sunrising It seems that Leetcode added some test cases. Your solution cannot be accepted.


  • 0
    S

    @wangxinbo Thanks for pointing out. I added this line:
    if(cur == 0) continue;
    after
    cur = x1*y2-x2*y1;


Log in to reply
 

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