469. Convex Polygon

• Difficulty: Medium

• Topics: Math

• Similar Questions:

Problem:

Given a list of points that form a polygon when joined sequentially, find if this polygon is convex (Convex polygon definition).

Note:

1. There are at least 3 and at most 10,000 points.
2. Coordinates are in the range -10,000 to 10,000.
3. You may assume the polygon formed by given points is always a simple polygon (Simple polygon definition). In other words, we ensure that exactly two edges intersect at each vertex, and that edges otherwise don't intersect each other.

Example 1:

[[0,0],[0,1],[1,1],[1,0]]

Answer: True

Explanation:

Example 2:

[[0,0],[0,10],[10,10],[10,0],[5,5]]

Answer: False

Explanation:

Solutions:

class Solution {
public:
    bool isConvex(vector<vector<int>>& points) {
        int direction = 0;
        int n = points.size();
        for (int i = 0; i < points.size(); ++i) {
            int newDirection = orientation(points[i%n], points[(i+1)%n], points[(i+2)%n]);
            if (newDirection == 0)  continue;
            if (newDirection * direction < 0)   return false;
            direction = newDirection;
        }
        return true;
    }

    int orientation(vector<int>& a, vector<int>& b, vector<int>& c) {
        vector<int> v1 = {b[0] - a[0], b[1] - a[1]};
        vector<int> v2 = {c[0] - b[0], c[1] - b[1]};

        int prodDiff = v1[0] * v2[1] - v1[1] * v2[0];
        if (prodDiff > 0)   return 1;
        else if (prodDiff < 0)   return -1;
        else return 0;
    }
};