LeetCode刷题实战469:凸多边形
共 2049字,需浏览 5分钟
·
2021-12-18 11:19
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.
示例
[[0,0],[0,1],[1,1],[1,0]]
输出:True
[[0,0],[0,10],[10,10],[10,0],[5,5]]
输出:False
解释:
解题
class Solution:
def isConvex(self, points: List[List[int]]) -> bool:
def cal_cross_product(A, B, C):
AB = [B[0] - A[0], B[1] - A[1]]
AC = [C[0] - A[0], C[1] - A[1]]
return AB[0] * AC[1] - AB[1] * AC[0]
flag = 0
n = len(points)
for i in range(n):
# cur > 0 表示points是按逆时针输出的;cur < 0,顺时针
cur = cal_cross_product(points[i], points[(i + 1) % n], points[(i + 2) % n])
if cur != 0:
# 说明异号, 说明有个角大于180度
if cur * flag < 0:
return False
else:
flag = cur
return True
LeetCode刷题实战462:最少移动次数使数组元素相等 II