Trees stand at distinct integer points. A rope is pulled tight around all of them. Write outer_trees(trees: list[list[int]]) -> list[list[int]] returning every tree that touches the rope: the corners where the rope bends and any tree lying on a straight stretch between two corners. Return them in any order, each once.
If all the trees lie on one line, every tree is on the fence.
outer_trees([[1, 1], [2, 2], [2, 0], [2, 4], [3, 3], [4, 2]])
# [[1,1], [2,0], [4,2], [3,3], [2,4]] in any order ([2,2] is strictly inside)
outer_trees([[1, 2], [2, 2], [4, 2]]) # all three: they're collinear
outer_trees([[0, 0], [0, 2], [2, 0], [2, 2], [1, 0]]) # all five: [1, 0] is on the bottom edge
Constraints: 1 ≤ len(trees) ≤ 3000, 0 ≤ x, y ≤ 100, all points distinct. Aim for O(n log n).
Show hint
The rope is the convex hull. After sorting the points by (x, y), you can build the lower and upper boundaries in one sweep each, discarding the last kept point whenever the turn it makes (the sign of a cross product) goes the wrong way. To keep trees lying on straight stretches, discard only on a strict wrong turn, not on a collinear one, and dedupe at the end.