Erect the Fence


Identifying Problem Isomorphism
“Erect the Fence” can be mapped to “Convex Hull”.
“Erect the Fence” asks you to construct a fence around a set of points, i.e., to identify the minimal convex polygon that contains all the points. This is equivalent to the computational geometry problem known as the “Convex Hull” problem.
Both problems deal with the idea of determining the smallest polygon that can encompass a given set of points. Therefore, the two problems can be viewed as conceptually similar. “Erect the Fence” is more complex because it’s embedded in a realworld context and could have more varied inputs.
10 Prerequisite LeetCode Problems
“587. Erect the Fence” is a geometric problem that involves the concept of the Convex Hull. Here are ten simpler problems to prepare for it:
“149. Max Points on a Line”: This is a problem about dealing with geometric concepts and points in a plane.
“447. Number of Boomerangs”: This problem involves distance computations between points in a 2D space.
“593. Valid Square”: This problem provides a basic understanding of geometric properties and computations.
“223. Rectangle Area”: This problem involves geometric computations in a 2D space.
“356. Line Reflection”: This problem deals with geometric transformations and point symmetry.
“836. Rectangle Overlap”: This problem involves determining overlapping regions between rectangles.
“939. Minimum Area Rectangle”: This problem requires understanding of geometric properties and computations.
“973. K Closest Points to Origin”: This problem involves sorting and computing distances in a 2D space.
“1037. Valid Boomerang”: This problem involves understanding of geometric properties in a 2D space.
“1232. Check If It Is a Straight Line”: This problem involves geometric computations in 2D space.


Problem Classification
Domain Classification: This problem belongs to the “Geometry” and “Optimization” domains. It involves the computation of geometrical properties and structures, and requires finding an optimal solution (minimum length of rope).
What components:
Input: An array ’trees’ where ’trees[i] = [xi, yi]’ represents the location of a tree in the garden.
Output: The output is a list of coordinates of trees that are exactly located on the fence perimeter.
Conditions: The goal is to enclose all trees using the minimum length of rope. All the trees must be enclosed to ensure the garden is wellfenced.
Problem Classification:
The problem can be classified as a “Computational Geometry” problem because it involves the use of geometry and mathematical concepts to solve a problem related to positioning and space. This kind of problem often includes computations based on points, lines, and polygons.
It’s also a “Optimization” problem as we are aiming to minimize the length of the rope used to fence the garden.
Lastly, the problem has elements of “Search” as we need to find and return the coordinates of trees exactly on the fence perimeter.
Language Agnostic Coding Drills
Understand the Problem Statement: The problem is to find all points that form the convex hull of a set of 2D points. The convex hull is the smallest convex polygon that contains all the points.
Break Down the Problem: The solution uses the Andrew’s monotone chain convex hull algorithm.
Sort: We need to sort the points based on their x and y coordinates.
Convex Hull Algorithm: We perform the algorithm on the sorted points and store the resultant points on the convex hull in the list.
Remove duplicate points: As the algorithm is performed twice (forward and backward), we might have some duplicate points. We need to remove them.
Return Result: Finally, return the points on the convex hull.
Drills Breakdown:
Sorting of points: Understand how to sort a list of 2D points. Points are sorted by their xcoordinate, and in case of a tie, by their ycoordinate.
Understanding of Convex Hull Algorithm: Learn how the Convex Hull Algorithm works, especially the Andrew’s monotone chain algorithm used in this solution. You need to understand the
ccw
function which calculates the cross product of the vectors formed by three points. If the cross product is less than zero, it means the points form a right turn which is not possible in convex hull.Itertools Usage: Understand how
itertools.chain
is used to iterate over the sorted points twice  once in the forward direction and once in the reverse.Points Removal: Understand how to remove duplicate points from the convex hull. As we perform the algorithm twice, it can lead to duplicate points on the hull which need to be removed.
Function Creation: Know how to wrap the algorithm in a function, taking care of the edge cases like if the points are less than or equal to 1, return the points as they are the convex hull.
Solution Approach: With the understanding of the drills, you can follow this approach to solve the problem.
If the points are less than or equal to 1, return the points.
Sort the points.
Perform the convex hull algorithm on the sorted points and store the points on the convex hull in a list.
Remove duplicate points from the hull.
Return the points on the hull.
Each drill is designed to tackle a part of the problem. Once you have a grasp of each drill, you can then integrate them into a single solution.
Targeted Drills in Python
 Sorting of points:


 Understanding of Convex Hull Algorithm: Here, we will focus on the
ccw
function used to determine the cross product.


 Itertools Usage: Here, we demonstrate how to use
itertools.chain
.


 Points Removal: This drill involves understanding how to remove duplicate points from a list. In the context of the problem, we would be removing points from the convex hull.


 Function Creation: This drill involves creating a function that wraps the entire process. A skeleton function is provided here as writing the entire function would combine the separate drills.


In the actual problem, the points removal step would be integrated within the Convex Hull Algorithm (specifically, when adding points to the hull list). The drills provide a way to focus on these individual aspects before they are combined to solve the full problem.