美文网首页
8.24 - hard - 105

8.24 - hard - 105

作者: 健时总向乱中忙 | 来源:发表于2017-08-25 09:39 被阅读0次

587. Erect the Fence

利用一种算法叫做Monotone Chain,加上之前的旋转卡壳。。。还有一道求是否所有点形成convex hull 这三个解法好好搞一搞清楚

    def outerTrees(self, points):
        """Computes the convex hull of a set of 2D points.

        Input: an iterable sequence of (x, y) pairs representing the points.
        Output: a list of vertices of the convex hull in counter-clockwise order,
          starting from the vertex with the lexicographically smallest coordinates.
        Implements Andrew's monotone chain algorithm. O(n log n) complexity.
        """

        # Sort the points lexicographically (tuples are compared lexicographically).
        # Remove duplicates to detect the case we have just one unique point.
        # points = sorted(set(points))
        points = sorted(points, key=lambda p: (p.x, p.y))

        # Boring case: no points or a single point, possibly repeated multiple times.
        if len(points) <= 1:
            return points

        # 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
        # Returns a positive value, if OAB makes a counter-clockwise turn,
        # negative for clockwise turn, and zero if the points are collinear.
        def cross(o, a, b):
            # return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
            return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)

        # Build lower hull
        lower = []
        for p in points:
            while len(lower) >= 2 and cross(lower[-2], lower[-1], p) < 0:
                lower.pop()
            lower.append(p)

        # Build upper hull
        upper = []
        for p in reversed(points):
            while len(upper) >= 2 and cross(upper[-2], upper[-1], p) < 0:
                upper.pop()
            upper.append(p)

        # Concatenation of the lower and upper hulls gives the convex hull.
        # Last point of each list is omitted because it is repeated at the
        # beginning of the other list.
        # return lower[:-1] + upper[:-1]
        return list(set(lower[:-1] + upper[:-1]))

相关文章

  • 8.24 - hard - 105

    587. Erect the Fence 利用一种算法叫做Monotone Chain,加上之前的旋转卡壳。。。还...

  • 8.24 - hard - 103

    564. Find the Closest Palindrome一道数学题。。。重点是找到各种情况并且对其简化。分...

  • 8.24 - hard - 104

    568. Maximum Vacation Days 又是一道dp,感觉用心去想还是可以做出来的,不过有点做不动了...

  • 8.24 - hard - 101

    546. Remove Boxes 先做出来一个backtracking的TLE版本,下面想想如何加memory,...

  • 8.24 - hard - 102

    552. Student Attendance Record II虽然知道这是一道DP题,但是这个dp状态真的很难...

  • 同舟人,誓相随,无畏更无惧

    8.24

  • 跑步第32天(37)

    8.24 休息

  • 2018-06-29

    8.24第一轮

  • 19/09/2017

    Work hard,play hard,study hard, love hard.一个小姐姐跟我这么说。她说后两...

  • 2019.8.24

    8.24 【阅读】8.24朗读《花钟》没有生字,可以有感情的读!8.23朗读《小鸡的家》三个生字, 【拼音】8.2...

网友评论

      本文标题:8.24 - hard - 105

      本文链接:https://www.haomeiwen.com/subject/jctudxtx.html