C++_AC


  • 0
    class Solution {
    public:
    bool isConvex(vector<vector<int>>& points) {
    int n = points.size();
    long check = 0;
    bool positive = false;
    bool negative = false;
    for(int i = 0; i < n; ++i){
        auto A = points[i];
        auto B = points[(i+1)%n];
        auto C = points[(i+2)%n];
        long tmp = CrossProduct(A,B,C);
        if(tmp > 0) positive = true;
        if(tmp < 0) negative = true;
        if(positive && negative) return false;
    }
    return true;
    

    }

    int CrossProduct(vector<int>& A, vector<int>& B, vector<int>& C){
    int X_AB = B[0] - A[0];
    int Y_AB = B[1] - A[1];
    int X_AC = C[0] - A[0];
    int Y_AC = C[1] - A[1];
    return X_AB*Y_AC - X_AC * Y_AB;
    

    }
    };


  • 0

    Actually, only comparing the sign of adjacent cross products is not enough because there could be 0's in between which won't fail condition check * tmp < 0 but the polygon might not be convex. OJ has just added new testing cases.


  • 0

    @zzg_zzm Hi, thanks for your comment. Yep, i tried to use two pointers to record the status of all cross products, if there are both positive & negative, return false.
    It seems that OJ take the "line" also as graph...

    Thank you so much!


  • 0

    @jasonshieh No problem. Yes, it is strange that straight lines are also considered as "convex polygons" (or actually checking for non-concaveness instead).

    Anyway, if OJ wants to rule straight lines out some day later, using return (positive || negative) at last line will get the edge case covered.


Log in to reply
 

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