0469：凸多边形（★）

力扣第 469 题

题目

给定 X-Y 平面上的一组点 points ，其中 points[i] = [xi, yi] 。这些点按顺序连成一个多边形。

如果该多边形为 凸 多边形（凸多边形的定义）则返回 true ，否则返回 false 。

你可以假设由给定点构成的多边形总是一个 简单的多边形（简单多边形的定义）。换句话说，我们要保证每个顶点处恰好是两条边的汇合点，并且这些边 互不相交 。

示例 1：

输入: points = [[0,0],[0,5],[5,5],[5,0]]
输出: true

示例 2：

输入: points = [[0,0],[0,10],[10,10],[10,0],[5,5]]
输出: false

提示:

• 3 <= points.length <= 104
• points[i].length == 2
• -104 <= xi, yi <= 104
• 所有点都 不同

分析

凸包问题，依次计算三个点构成的两个向量的叉乘，法向量方向不发生改变则是凸多边形 。

解答

1
2
3
4
5
6
7

def isConvex(self, points: List[List[int]]) -> bool:
	def cal(a, b, c):
		return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])

	P, n = points, len(points)
	A = [cal(P[i], P[(i+1)%n], P[(i+2)%n]) for i in range(n)]
	return all(val<=0 for val in A) or all(val>=0 for val in A)

48 ms