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

Note:

There are at least 3 and at most 10,000 points. Coordinates are in the range -10,000 to 10,000. 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:

Solution

public class Solution {
    public boolean isConvex(List<List<Integer>> points) {
        // every two consequtive points can form a line, all other points should have the same sign
        if(points.size() < 3) return false;

        List<Integer> p1 = points.get(0);
        List<Integer> p2 = points.get(1);

        // find the third point that is not in the same line
        int idx3 = -1;
        for(int i = 2; i < points.size(); i++) {
            if(getDirection(points.get(0), points.get(1), points.get(i)) != 0) {
                idx3 = i;
                break;
            }
        }
        if(idx3 == -1) return false;
        List<Integer> p3 = points.get(idx3);

        boolean dir = getDirection(p1, p2, p3) > 0;
        for(int i = idx3; i <= points.size(); i++) {
            // the next point need to fall in the right range
            List<Integer> pprev = points.get(i-1);
            List<Integer> pnow = points.get(i%points.size());
            List<Integer> pnext = points.get((i+1)%points.size());

            int cur = getDirection(pprev, pnow, pnext);
            if(cur != 0 && (cur > 0) != dir) return false;
        }

        return true;
    }

    public int getDirection(List<Integer> p1, List<Integer> p2, List<Integer> p3) {
        return (p3.get(1)-p2.get(1))*(p1.get(0)-p2.get(0)) - (p1.get(1)-p2.get(1))*(p3.get(0)-p2.get(0));
    }
}