Erect the Fence
Hard · Geometry · Array · Math · Geometry
Problem
A garden has trees at the positions trees[i] = [x, y]. You want to put one fence around the whole garden using as little fence as possible, so that every tree is inside the fence or on it.
Return the positions of every tree that lies on the fence, in any order. That includes trees in the middle of a straight stretch of fence, not only the trees at its corners.
The shortest fence is the boundary of the convex hull of the trees. If all the trees stand on one line, the fence runs along that line, and every tree is on it.
Examples
Input: trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]] Output: [[2,4],[3,3],[1,1],[2,0],[4,2]]
The fence goes through (1, 1), (2, 0), (4, 2), (3, 3) and (2, 4). The tree at (2, 2) is inside it. Note that (3, 3) is on the straight stretch from (4, 2) to (2, 4), and it is part of the answer.
Input: trees = [[1,2],[2,2],[4,2]] Output: [[1,2],[2,2],[4,2]]
All three trees are on the line y = 2, so the fence runs along that line and touches every tree.
Constraints
- 1 <= len(trees) <= 3000
- trees[i] == [x, y]
- 0 <= x, y <= 100
- all positions are distinct
Approaches
- Corners first, then every tree on an edge — time O(n log n + n · h), h the number of corners, space O(n)
Follow-up
What if only the corners of the fence are wanted? Pop on cross <= 0 instead of cross < 0; the chains then keep only the corners and share nothing but the two ends. That version is the one to use for the fence’s length or the area it encloses.
Related problems
Start free on Cariara · Coding problems · System design studio
