469. Convex Polygon 凸多边形

题目地址：https://leetcode-cn.com/problems/convex-polygon/

题目描述

Given a list of points that form a polygon when joined sequentially, find if this polygon is convex (Convex polygon definition).

Note:

1、 Thereareatleast3andatmost10,000points.；
2、 Coordinatesareintherange-10,000to10,000.；
3、 Youmayassumethepolygonformedbygivenpointsisalwaysasimplepolygon(Simplepolygondefinition).Inotherwords,weensurethatexactlytwoedgesintersectateachvertex,andthatedgesotherwisedon'tintersecteachother.；

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:

题目大意

判断一个多边形是不是凸多边形。

解题方法

计算向量夹角

借鉴了参考资料中的做法：

假设多边形的顶点是呈逆时针排列的，多边形是凸多边形的充要条件是：对于多边形的任何一条边，其下一条边必须是不朝右拐的（可以向左拐，也可以不拐）。那么如何判断下一条边是不朝右拐呢？假设假设当前边形成的向量是v1，下一条边形成的向量是v2，那么v2不朝右拐的充要条件是v1 x v2 >= 0，也就是它们形成的有向三角形的面积大于等于0，符合右手法则。

C++代码如下：

class Solution {
public:
    bool isConvex(vector<vector<int>>& points) {
        int N = points.size();
        long pre = 0;
        for (int i = 0; i < N; ++i) {
            long cur = angle({points[i], points[(i + 1) % N], points[(i + 2) % N]});
            if (cur != 0) {
                if (cur * pre < 0)
                    return false;
                else
                    pre = cur;
            }
        }
        return true;
    }
    int angle(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]);

    }
};

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

参考资料：https://blog.csdn.net/magicbean2/article/details/78593338

2022

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发