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
Return the coordinates of the trees that lie exactly on the fence perimeter. You can return the answer in any order.
Constraints:
1≤ trees.length≤300 trees[i].length==2 0≤ xi,yi≤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 to right. For each new point, we check whether it creates a right turn (i.e., stepping inward, making the shape non-convex) or not with the last two points already in the hull using the orientation formula. This is done using the cross product formula, which tells us whether the turn is left, right, or collinear. If a right turn occurs, we remove the last added point until the shape remains convex.
The orientation formula helps us determine the turning direction when moving from one point to another.
Suppose we’re walking from point
p toq , then tor . The formula tells us if this turn is a left turn (anticlockwise), a right turn (clockwise), or no turn (the three points lie in a straight line—collinear).
...
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
Return the coordinates of the trees that lie exactly on the fence perimeter. You can return the answer in any order.
Constraints:
1≤ trees.length≤300 trees[i].length==2 0≤ xi,yi≤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 to right. For each new point, we check whether it creates a right turn (i.e., stepping inward, making the shape non-convex) or not with the last two points already in the hull using the orientation formula. This is done using the cross product formula, which tells us whether the turn is left, right, or collinear. If a right turn occurs, we remove the last added point until the shape remains convex.
The orientation formula helps us determine the turning direction when moving from one point to another.
Suppose we’re walking from point
p toq , then tor . The formula tells us if this turn is a left turn (anticlockwise), a right turn (clockwise), or no turn (the three points lie in a straight line—collinear).
...