LeetCode469 - Convex Polygon - Medium (Python)

ladysosoli 2020-01-30

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

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

Answer: True
[[0,0],[0,10],[10,10],[10,0],[5,5]]

Answer: False思路:这题问的是给一系列polygon的点,判断其是否是convex的。一个比较好的判断方法是看所有点是否是按照同一个顺序排列的,比如所有点都是依次顺时针,逆时针或者是同一条线排列。这里判断方向的方法,用到了LeetCode上有人po的 Robert Sedgewick‘s Algorithm Course里的内容。判断三个点是否按照某一个方向排列,我们可以先计算(b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])。 如果这个值大于0,那么意味着是逆时针的,如果小于0,那么是顺时针。如果等于0,那么意味着是同一条线上排列的。所以我们可以依次对points中的每三个点进行上述公式的计算,以及保存之前三个点的方向和此时三个点的方向,如果出现不一致,那么我们可以直接return False。需要注意的是这个计算也是从i=0开始的,当i=0的时候,判断的点刚好是points[-2], points[-1], points[0]. 这题的难点在于如何判断Convex。
class Solution:
    def isConvex(self, points: List[List[int]]) -> bool:
        def direction(a,b,c):
            return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])
        d = None
        for i in range(len(points)):
            a = direction(points[i-2],points[i-1],points[i])
            if a == 0: continue
            if d == None: d = a
            else:
                if a*d < 0: return False
        
        return True

相关推荐