Description#
You are given an array of points on the X-Y plane points
where points[i] = [xi, yi]
. The points form a polygon when joined sequentially.
Return true
if this polygon is convex and false
otherwise.
You may assume the polygon formed by given points is always a simple polygon. In other words, we ensure that exactly two edges intersect at each vertex and that edges otherwise don't intersect each other.
Example 1:
![](https://spcdn.pages.dev/leetcode/problems/0469.Convex%20Polygon/images/covpoly1-plane.jpg)
Input: points = [[0,0],[0,5],[5,5],[5,0]]
Output: true
Example 2:
![](https://spcdn.pages.dev/leetcode/problems/0469.Convex%20Polygon/images/covpoly2-plane.jpg)
Input: points = [[0,0],[0,10],[10,10],[10,0],[5,5]]
Output: false
Constraints:
3 <= points.length <= 104
points[i].length == 2
-104 <= xi, yi <= 104
- All the given points are unique.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution:
def isConvex(self, points: List[List[int]]) -> bool:
n = len(points)
pre = cur = 0
for i in range(n):
x1 = points[(i + 1) % n][0] - points[i][0]
y1 = points[(i + 1) % n][1] - points[i][1]
x2 = points[(i + 2) % n][0] - points[i][0]
y2 = points[(i + 2) % n][1] - points[i][1]
cur = x1 * y2 - x2 * y1
if cur != 0:
if cur * pre < 0:
return False
pre = cur
return True
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public boolean isConvex(List<List<Integer>> points) {
int n = points.size();
long pre = 0, cur = 0;
for (int i = 0; i < n; ++i) {
var p1 = points.get(i);
var p2 = points.get((i + 1) % n);
var p3 = points.get((i + 2) % n);
int x1 = p2.get(0) - p1.get(0);
int y1 = p2.get(1) - p1.get(1);
int x2 = p3.get(0) - p1.get(0);
int y2 = p3.get(1) - p1.get(1);
cur = x1 * y2 - x2 * y1;
if (cur != 0) {
if (cur * pre < 0) {
return false;
}
pre = cur;
}
}
return true;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
bool isConvex(vector<vector<int>>& points) {
int n = points.size();
long long pre = 0, cur = 0;
for (int i = 0; i < n; ++i) {
int x1 = points[(i + 1) % n][0] - points[i][0];
int y1 = points[(i + 1) % n][1] - points[i][1];
int x2 = points[(i + 2) % n][0] - points[i][0];
int y2 = points[(i + 2) % n][1] - points[i][1];
cur = 1L * x1 * y2 - x2 * y1;
if (cur != 0) {
if (cur * pre < 0) {
return false;
}
pre = cur;
}
}
return true;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| func isConvex(points [][]int) bool {
n := len(points)
pre, cur := 0, 0
for i := range points {
x1 := points[(i+1)%n][0] - points[i][0]
y1 := points[(i+1)%n][1] - points[i][1]
x2 := points[(i+2)%n][0] - points[i][0]
y2 := points[(i+2)%n][1] - points[i][1]
cur = x1*y2 - x2*y1
if cur != 0 {
if cur*pre < 0 {
return false
}
pre = cur
}
}
return true
}
|