Algorithm Practice
Search…
469 Convex Polygon
1. Question
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:
1
[[0,0],[0,1],[1,1],[1,0]]
2
3
Answer: True
4
5
Explanation:
Copied!
Example 2:
1
[[0,0],[0,10],[10,10],[10,0],[5,5]]
2
3
Answer: False
4
5
Explanation:
Copied!
2. Implementation
(1) Geometry
思路: 凸多边形的定义是每个顶点的角度都小于180度, 判断一个多边形
要注意的地方有两点：(1)如果cross product是0，我们应该忽略，否则会影响之后的结果. (2)由于数字可能溢出，所以curCroosProduct和preCrossProduct要用long
1
class Solution {
2
public boolean isConvex(List<List<Integer>> points) {
3
int n = points.size();
4
long curCrossProduct = 0;
5
long preCrossProduct = 0;
6
7
for (int i = 0; i < n; i++) {
8
List<Integer> pointA = points.get(i);
9
List<Integer> pointB = points.get((i + 1) % n);
10
List<Integer> pointC = points.get((i + 2) % n);
11
12
curCrossProduct = getCrossProduct(pointA, pointB, pointC);
13
14
if (curCrossProduct != 0) {
15
if (curCrossProduct * preCrossProduct < 0) {
16
return false;
17
}
18
preCrossProduct = curCrossProduct;
19
}
20
}
21
return true;
22
}
23
24
public int getCrossProduct(List<Integer> pointA, List<Integer> pointB, List<Integer> pointC) {
25
int BAx = pointB.get(0) - pointA.get(0);
26
int BAy = pointB.get(1) - pointA.get(1);
27
int CAx = pointC.get(0) - pointA.get(0);
28
int CAy = pointC.get(1) - pointA.get(1);
29
30
return BAx * CAy - CAx * BAy;
31
}
32
}
Copied!
3. Time & Space Complexity
时间复杂度O(n), n是顶点的个数, 空间复杂度O(1)
Last modified 2yr ago