<gh_stars>1-10
# Time:  O(nlogn)
# Space: O(n)

# There are some trees, where each tree is represented by
# (x,y) coordinate in a two-dimensional garden.
# Your job is to fence the entire garden using the minimum length of rope
# as it is expensive. The garden is well fenced only if all the trees are enclosed.
# Your task is to help find the coordinates of trees which are exactly located on the fence perimeter.
#
# Example 1:
# Input: [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
# Output: [[1,1],[2,0],[4,2],[3,3],[2,4]]
#
# Example 2:
# Input: [[1,2],[2,2],[4,2]]
# Output: [[1,2],[2,2],[4,2]]
#
# Even you only have trees in a line, you need to use rope to enclose them.
# Note:
#
# All trees should be enclosed together.
# You cannot cut the rope to enclose trees that will separate them in more than one group.
# All input integers will range from 0 to 100.
# The garden has at least one tree.
# All coordinates are distinct.
# Input points have NO order. No order required for output.

# Definition for a point.
# class Point(object):
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b

import itertools


# Monotone Chain Algorithm
class Solution(object):
    def outerTrees(self, points):
        """
        :type points: List[List[int]]
        :rtype: List[List[int]]
        """
        def ccw(A, B, C):
            return (B[0]-A[0])*(C[1]-A[1]) - (B[1]-A[1])*(C[0]-A[0])

        if len(points) <= 1:
           return points

        hull = []
        points.sort()
        for i in itertools.chain(xrange(len(points)), reversed(xrange(len(points)-1))):
            while len(hull) >= 2 and ccw(hull[-2], hull[-1], points[i]) < 0:
                hull.pop()
            hull.append(points[i])
        hull.pop()

        for i in xrange(1, (len(hull)+1)//2):
            if hull[i] != hull[-1]:
                break
            hull.pop()
        return hull

# Time:  O(nlogn)
# Space: O(n)

# There are some trees, where each tree is represented by
# (x,y) coordinate in a two-dimensional garden.
# Your job is to fence the entire garden using the minimum length of rope
# as it is expensive. The garden is well fenced only if all the trees are enclosed.
# Your task is to help find the coordinates of trees which are exactly located on the fence perimeter.
#
# Example 1:
# Input: [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
# Output: [[1,1],[2,0],[4,2],[3,3],[2,4]]
#
# Example 2:
# Input: [[1,2],[2,2],[4,2]]
# Output: [[1,2],[2,2],[4,2]]
#
# Even you only have trees in a line, you need to use rope to enclose them.
# Note:
#
# All trees should be enclosed together.
# You cannot cut the rope to enclose trees that will separate them in more than one group.
# All input integers will range from 0 to 100.
# The garden has at least one tree.
# All coordinates are distinct.
# Input points have NO order. No order required for output.

# Definition for a point.
# class Point(object):
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b

import itertools


# Monotone Chain Algorithm
class Solution(object):
    def outerTrees(self, points):
        """
        :type points: List[List[int]]
        :rtype: List[List[int]]
        """
        def ccw(A, B, C):
            return (B[0]-A[0])*(C[1]-A[1]) - (B[1]-A[1])*(C[0]-A[0])

        if len(points) <= 1:
           return points

        hull = []
        points.sort()
        for i in itertools.chain(xrange(len(points)), reversed(xrange(len(points)-1))):
            while len(hull) >= 2 and ccw(hull[-2], hull[-1], points[i]) < 0:
                hull.pop()
            hull.append(points[i])
        hull.pop()

        for i in xrange(1, (len(hull)+1)//2):
            if hull[i] != hull[-1]:
                break
            hull.pop()
        return hull
# Time:  O(nlogn) # Space: O(n) # There are some trees, where each tree is represented by # (x,y) coordinate in a two-dimensional garden. # Your job is to fence the entire garden using the minimum length of rope # as it is expensive. The garden is well fenced only if all the trees are enclosed. # Your task is to help find the coordinates of trees which are exactly located on the fence perimeter. # # Example 1: # Input: [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]] # Output: [[1,1],[2,0],[4,2],[3,3],[2,4]] # # Example 2: # Input: [[1,2],[2,2],[4,2]] # Output: [[1,2],[2,2],[4,2]] # # Even you only have trees in a line, you need to use rope to enclose them. # Note: # # All trees should be enclosed together. # You cannot cut the rope to enclose trees that will separate them in more than one group. # All input integers will range from 0 to 100. # The garden has at least one tree. # All coordinates are distinct. # Input points have NO order. No order required for output. # Definition for a point. # class Point(object): #     def __init__(self, a=0, b=0): #         self.x = a #         self.y = b # Monotone Chain Algorithm :type points: List[List[int]]         :rtype: List[List[int]]