You are given an array trees where trees[i] = [xi, yi] represents the location of a tree in the garden.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.Return the coordinates of trees that are exactly located on the fence perimeter. You may return the answer in any order.
Input: trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]Output: [[1,1],[2,0],[4,2],[3,3],[2,4]]Explanation: All the trees will be on the perimeter of the fence except the tree at [2, 2], which is inside the fence.
Input: trees = [[1,2],[2,2],[4,2]]Output: [[4,2],[2,2],[1,2]]Explanation: The fence forms a line that passes through all the trees.
class Solution: # Time: O(n log n) # Space: O(n) def outer_trees(self, trees: list[list[int]]) -> list[list[int]]: points = sorted(tuple(p) for p in trees) def cross(i: int, j: int, k: int) -> int: a, b, c = points[i], points[j], points[k] return (b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0]) n = len(points) if n < 4: return [list(p) for p in points] visited = [False] * n stack = [0] for i in range(1, n): while len(stack) > 1 and cross(stack[-2], stack[-1], i) < 0: visited[stack.pop()] = False visited[i] = True stack.append(i) lower_hull_size = len(stack) for i in range(n - 2, -1, -1): if visited[i]: continue while len(stack) > lower_hull_size and cross(stack[-2], stack[-1], i) < 0: stack.pop() stack.append(i) stack.pop() return [list(points[i]) for i in stack]
