Hard

Quiz

#587 Erect the Fence

APPROACH

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.

1 of 4

1:00

What is the optimal approach for this problem?