LC469. Convex Polygon
Given a list of points that form a polygon when joined sequentially, find if this polygon is convex (Convex polygon definition).
Example 1:
[[0,0],[0,1],[1,1],[1,0]]
Answer: True
Example 2:
[[0,0],[0,10],[10,10],[10,0],[5,5]]
Answer: False
数学问题，凸多边形的话，我知道是所有的点都在任取一条变的一侧，也可以说是每个夹角都在[0, 180]度。👇分析写的挺好的。
总之对每相邻两边进行判断， 所有的夹角符合同一个要求就好。
public class Solution {
public boolean isConvex(List<List<Integer>> points) {
// for a series of points, calculate crossProduct of each two edges
// depends on its order, they should be the all > 0 or < 0
if(points == null || points.size() == 0) return false;
boolean positive = false, negative = false;
int num = points.size();
for(int i = 0; i < num; i++){
// if i = 0 or i = num - 1
List<Integer> point = points.get(i);
List<Integer> next = points.get((i + 1)%num);
List<Integer> pre = points.get((i - 1+num)%num);
int cp = crossProduct(pre, point, next);
if(cp > 0) positive = true;
if(cp < 0) negative = true;
if(positive && negative) return false;
}
return true;
} // isConvex
private int crossProduct(List<Integer> pre, List<Integer> cur, List<Integer> next){
return (cur.get(0) - pre.get(0))*(cur.get(1) - next.get(1)) - (cur.get(1) - pre.get(1))*(cur.get(0) - next.get(0));
} // crossProduct
}
O(n).