​LeetCode刷题实战469:凸多边形

程序IT圈

共 2049字,需浏览 5分钟

 ·

2021-12-18 11:19

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 凸多边形,我们先来看题面:
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:

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.



给定一个按顺序连接的多边形的顶点,判断该多边形是否为凸多边形。(凸多边形的定义)

注:
顶点个数至少为 3 个且不超过 10,000。
坐标范围为 -10,000 到 10,000。
你可以假定给定的点形成的多边形均为简单多边形(简单多边形的定义)。换句话说,保
每个顶点处恰好是两条边的汇合点,并且这些边 互不相交 。

示例                             

示例 1:
[[0,0],[0,1],[1,1],[1,0]]

输出:True
解释:
示例 2:
[[0,0],[0,10],[10,10],[10,0],[5,5]]

输出:False

解释:


解题

叉乘判断

设A(x1,y1),B(x2,y2),C(x3,y3)则三角形两边的矢量分别是:

AB=(x2-x1,y2-y1), AC=(x3-x1,y3-y1)

则AB和AC的叉积为:(2*2的行列式) 值为:(x2-x1)*(y3-y1) - (y2-y1)*(x3-x1)

利用右手法则进行判断:

如果AB*AC>0,则三角形ABC是逆时针的

如果AB*AC<0,则三角形ABC是顺时针的

因为不知道顶点是顺时针输入,还是逆时针输入,所以要记录符号,后面点叉乘如果一样就是凸多边形。

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


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:

LeetCode1-460题汇总,希望对你有点帮助!

LeetCode刷题实战461:汉明距离

LeetCode刷题实战462:最少移动次数使数组元素相等 II

LeetCode刷题实战463:岛屿的周长

LeetCode刷题实战464:我能赢吗

LeetCode刷题实战465:最优账单平衡

LeetCode刷题实战466:统计重复个数

LeetCode刷题实战467:环绕字符串中唯一的子字符串

LeetCode刷题实战468:验证IP地址



浏览 24
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报