[Leetcode] 469. Convex Polygon 解题报告_4-vertex polygon. coordinates in cell-CSDN博客

本文链接：https://blog.csdn.net/magicbean2/article/details/78593338

该博客详细介绍了LeetCode 469题目的解题思路，即判断给定点列表是否形成一个凸多边形。博主通过计算几何的方法，提出当多边形顶点逆时针排列时，如果每条边的下一条边向量与当前边向量的叉积大于等于0，则多边形为凸多边形。算法的时间复杂度为O(n)，空间复杂度为O(1)。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目：

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.

Example 1:

[[0,0],[0,1],[1,1],[1,0]]

Answer: True

Explanation:

Example 2:

[[0,0],[0,10],[10,10],[10,0],[5,5]]

Answer: False

Explanation:

思路：

一道计算几何的基础题目，上次面试Google就挂在一道计算几何题目上了。为了便于说明，我们假设多边形的顶点是呈逆时针排列的，那么该多边形是凸多边形的充要条件是：对于多边形的任何一条边，其下一条边必须是不朝右拐的（可以向左拐，也可以不拐）。那么如何判断下一条边是不朝右拐呢？假设假设当前边形成的向量是v1，下一条边形成的向量是v2，那么v2不朝右拐的充要条件是v1 x v2 >= 0，也就是它们形成的有向三角形的面积大于等于0，符合右手法则。

对于多边形顶点呈顺时针排列的情况，判断方式刚好相反。该算法的时间复杂度是O(n)，空间复杂度是O(1)。

代码：

class Solution {
public:
    bool isConvex(vector<vector<int>>& points) {
        for (long i = 0, n = points.size(), prev = 0, cur; i < n; ++i) {
            cur = det2({points[i], points[(i + 1 )% n], points[(i + 2) % n]});
            if (cur != 0) {
                if (cur * prev < 0) {
                    return false;
                }
                else {
                    prev = cur;
                }
            }
        }
        return true;
    }
private:
    long det2(const vector<vector<int>>& A) {
    	return (A[1][0]-A[0][0])*(A[2][1]-A[0][1]) - (A[1][1]-A[0][1])*(A[2][0]-A[0][0]);
    }
};