#587

Erect the Fence

candidate master · 1390 · lc hard +32 · verified · 52.8% accepted · 1,542 likes · top 43%

Description

You are given an array trees where trees[i] = [xi, yi] is the 2D position of a tree. Surround all trees with the shortest possible fence (the convex hull perimeter). Return the coordinates of every tree that lies exactly on the fence. The answer may be in any order.

Example 1:

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 will be inside the fence.

Example 2:

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.

Code

1

2

3

class Solution:
    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:

class Solution:
    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]: