LeetCode 469题是关于判断一个多边形是否为凸多边形的问题。凸多边形是指所有内角都小于180度的多边形，或者等价地说，多边形上任意两点的连线都在多边形内部。

题目描述

给定一个多边形的所有顶点坐标，你需要判断这个多边形是否为凸多边形。

输入

一个二维数组 points，其中每个元素是一个长度为2的数组，表示多边形的一个顶点的坐标。

输出

返回一个布尔值，表示这个多边形是否为凸多边形。

示例

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

输入: points = [[0,0],[0,1],[1,0]] 输出: false

解题思路

判断一个多边形是否为凸多边形可以通过计算相邻边之间的叉积（cross product）来实现。具体步骤如下：

1. 计算叉积： 对于多边形的每三个连续顶点 (A, B, C)，计算向量 (AB) 和 (BC) 的叉积。叉积的符号可以告诉我们 (B) 点处的转向是左转还是右转。
2. 判断转向：
   • 如果所有相邻边的叉积符号相同（全为正或全为负），则多边形为凸多边形。
   • 如果叉积符号不一致，则多边形不是凸多边形。
3. 处理边界情况：
   • 多边形至少需要3个顶点才能构成一个多边形。
   • 需要考虑顶点顺序的影响，可以统一按照顺时针或逆时针顺序处理。

代码实现

以下是使用Python实现的代码示例：

def isConvex(points): def cross_product(o, a, b):

    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

n = len(points)
if n < 3:
    return False

# 初始化前两个边的叉积符号
pre = 0
for i in range(n):
    # 当前点、下一个点和下下个点
    cur = cross_product(points[i], points[(i + 1) % n], points[(i + 2) % n])
    if cur != 0:
        if pre * cur < 0:
            return False
        pre = cur

return True

print(isConvex(points1)) # 输出: True print(isConvex(points2)) # 输出: False

解释

1. cross_product函数：计算两个向量的叉积。
2. 主函数isConvex：
   • 首先检查顶点数量是否小于3，如果是则直接返回False。
   • 使用一个循环遍历所有顶点，计算每三个连续顶点形成的两个向量的叉积。
   • 如果叉积不为0，检查当前叉积与前一个叉积的符号是否相反，如果是则返回False。
   • 如果所有叉积符号一致，则返回True。

通过这种方法，可以有效地判断一个多边形是否为凸多边形。希望这个解释对你理解并解决LeetCode 469题有所帮助！