Tuesday, December 25, 2018

469. Convex Polygon



if tmp == 0, a -> b 180° on the same line;
elif tmp > 0, a -> b clockwise;
else tmp < 0, a -> anticlockwise;

float BAx = Ax - Bx;
    float BAy = Ay - By;
    float BCx = Cx - Bx;
    float BCy = Cy - By;

    // Calculate the Z coordinate of the cross product.
    return (BAx * BCy - BAy * BCx);
如果cross product = 0证明在同一条直线上,需要直接skip
63.79 %
class Solution {
    public boolean isConvex(List<List<Integer>> points) {
        if (points == null || points.size() <= 2) return false;
        int len = points.size();
        Integer prev = null;
        for (int i = 0; i < len; i++) {
            List<Integer> A = i == 0 ? points.get(len - 1) : points.get(i - 1);
            List<Integer> B = points.get(i);
            List<Integer> C = i == len - 1 ? points.get(0) : points.get(i + 1);
            int BAx = A.get(0) - B.get(0);
            int BAy = A.get(1) - B.get(1);
            int BCx = C.get(0) - B.get(0);
            int BCy = C.get(1) - B.get(1);
            int curr = BAx * BCy - BAy * BCx;
            // System.out.println(i + " " + curr);
            if (curr == 0) continue;
            if (prev == null) {
                prev = curr > 0 ? 1 : -1;
            } else if (prev * curr < 0) {
                return false;
            }
        }
        return true;
    }
}



No comments:

Post a Comment