Solution: Erect the Fence

Statement

You are given an array of points, trees, where trees[i] = [xᵢ, yᵢ] represents the location of a tree on a 2D plane. Your goal is to enclose all the trees using the shortest possible length of rope, forming a fence around the garden. A garden is considered well-fenced if every tree lies inside or on the boundary of the fence (i.e., the fence forms the convex hullThis is the smallest convex shape, completely encloses a set of points. of all the points).

Return the coordinates of the trees that lie exactly on the fence perimeter. You can return the answer in any order.

Constraints:

• $1 \leq$ trees.length $\leq 300$

• trees[i].length == $2$

• $0 \leq$ xi, yi $\leq 100$

• All the given positions are unique.

Solution

Imagine we have a set of nails hammered into a wooden board—each nail represents a point from trees. Now, if we stretch a rubber band around a group of nails and let it wrap around them completely, the boundary it forms is called the convex hull. It covers all the outer points and leaves out the ones inside.

The convex hull is the smallest convex polygon that completely encloses all the given points. It includes the points on the outside edge, while any points strictly inside are not part of the hull. The convex hull makes sure the shape has no dents or curves inward.

We want to achieve a similar thing. In this problem, we want to build a fence around all the trees using the least amount of rope, i.e., we need the tightest possible loop that encloses every tree. By computing the convex hull of the tree positions, we find out which trees must lie on the perimeter of the fence. These are the trees we can’t skip, because leaving any of them out would make the fence miss some part of the garden.

An efficient method for computing the convex hull of a set of points is the Monotone Chain algorithm. The process begins by sorting the points lexicographically, first by their x-coordinate and then by their y-coordinate if the x-coordinates are the same. This ensures a structured order for constructing the convex boundary as we first traverse from “left to right” and later “right to left”.

Once sorted, we construct the lower hull by iterating through the points from left ...