# Erect the Fence
**Difficulty:** HARD
[External](https://leetcode.com/problems/erect-the-fence)
Canonical: https://scaleengineer.com/dsa/problems/erect-the-fence
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry)
**Data structures:** Array
---
## Problem
You are given an array `trees` where `trees[i] = [xi, yi]` represents the location of a tree in the garden.

Fence the entire garden using the minimum length of rope, as it is expensive. The garden is well-fenced only if **all the trees are enclosed**.

Return _the coordinates of trees that are exactly located on the fence perimeter_. You may return the answer in **any order**.

**Example 1:**

![](https://assets.glich.co/dsa/erect-the-fence/image0.jpg) 

**Input:** trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
**Output:** [[1,1],[2,0],[4,2],[3,3],[2,4]]
**Explanation:** All the trees will be on the perimeter of the fence except the tree at [2, 2], which will be inside the fence.

**Example 2:**

![](https://assets.glich.co/dsa/erect-the-fence/image1.jpg) 

**Input:** trees = [[1,2],[2,2],[4,2]]
**Output:** [[4,2],[2,2],[1,2]]
**Explanation:** The fence forms a line that passes through all the trees.

**Constraints:**

* `1 <= trees.length <= 3000`
* `trees[i].length == 2`
* `0 <= xi, yi <= 100`
* All the given positions are **unique**.

# Approaches
## Jarvis's March (Gift Wrapping)
This approach, also known as the Gift Wrapping algorithm, simulates wrapping a string around the set of points. It starts from an extreme point (e.g., the leftmost one) and iteratively finds the next point on the hull by selecting the one that creates the most "counter-clockwise" turn. This process continues until the hull wraps back to the starting point.
**Time:** O(N * H), where N is the total number of trees and H is the number of trees on the fence. For each of the H hull points, we iterate through all N points to find the next one. In the worst case, H can be equal to N, leading to a time complexity of O(N^2). · **Space:** O(N) to store the hull points. In the worst case, all N points are on the hull.
**Pros:** Conceptually simple and easy to understand the high-level idea.; It's an output-sensitive algorithm, meaning its performance depends on the number of hull points (H). It's efficient if H is small.
**Cons:** The worst-case time complexity of O(N^2) makes it unsuitable for large datasets.; The implementation can be tricky, especially the logic to correctly handle collinear points to ensure all boundary points are included without errors.
### Explanation
The Jarvis's March algorithm is one of the simplest ways to compute the convex hull. It builds the hull one point at a time.

Here's a step-by-step breakdown:
1.  **Find a starting point**: We must begin with a point that is guaranteed to be on the hull. The point with the minimum x-coordinate (the leftmost point) is a perfect candidate. In case of a tie, the one with the minimum y-coordinate is chosen.
2.  **Iterative Wrapping**: From the current hull point `p`, we search for the next hull point `q`. We iterate through all other points `r` and find the one that has the smallest polar angle with respect to `p`. This is equivalent to finding the point `r` that makes the most counter-clockwise turn from the vector extending from `p`. The orientation can be determined using the cross product of vectors `(p, q)` and `(p, r)`.
3.  **Handling Collinearity**: A crucial part of the algorithm is handling points that are collinear. When we find the next point `q`, we must also include any points that lie on the line segment between the current point `p` and `q`. These points are part of the fence.
4.  **Termination**: We add the newly found point(s) to our hull and repeat the process from the new point. The algorithm terminates when we wrap around and select our original starting point as the next point.

```java
class Solution {
    // Returns a value indicating the orientation of the triplet (p, q, r)
    // > 0: Counter-clockwise (left turn)
    // < 0: Clockwise (right turn)
    // = 0: Collinear
    private int orientation(int[] p, int[] q, int[] r) {
        return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]);
    }

    // Returns the squared Euclidean distance between two points
    private int distanceSq(int[] p, int[] q) {
        return (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
    }

    public int[][] outerTrees(int[][] trees) {
        if (trees.length <= 3) {
            return trees;
        }

        Set<int[]> hull = new HashSet<>();

        // Find the leftmost point
        int startIdx = 0;
        for (int i = 1; i < trees.length; i++) {
            if (trees[i][0] < trees[startIdx][0]) {
                startIdx = i;
            }
        }

        int currentIdx = startIdx;
        do {
            int nextIdx = (currentIdx + 1) % trees.length;
            // Find the next point on the hull
            for (int i = 0; i < trees.length; i++) {
                int orient = orientation(trees[currentIdx], trees[nextIdx], trees[i]);
                if (orient > 0) { // trees[i] is more counter-clockwise
                    nextIdx = i;
                } else if (orient == 0) { // Collinear case
                    // If trees[i] is farther from currentIdx, it's a better candidate
                    if (distanceSq(trees[currentIdx], trees[i]) > distanceSq(trees[currentIdx], trees[nextIdx])) {
                        nextIdx = i;
                    }
                }
            }

            // Add all points on the segment from currentIdx to nextIdx
            for (int i = 0; i < trees.length; i++) {
                if (orientation(trees[currentIdx], trees[nextIdx], trees[i]) == 0) {
                    hull.add(trees[i]);
                }
            }
            currentIdx = nextIdx;
        } while (currentIdx != startIdx);

        return hull.toArray(new int[hull.size()][]);
    }
}
```
### Algorithm
- Find the point with the smallest x-coordinate (leftmost point). If there's a tie, pick the one with the smallest y-coordinate. This point is guaranteed to be on the convex hull and will be our starting point.
- Start with the leftmost point as the current point `p`.
- Repeatedly find the next point `q` on the hull. The point `q` is chosen such that for any other point `r`, the triplet `(p, q, r)` forms a counter-clockwise turn or is collinear. This means `q` is the most counter-clockwise point with respect to `p`.
- To handle collinear points, if multiple points are equally counter-clockwise (i.e., they are collinear with `p`), the one farthest from `p` is chosen as the next vertex `q`.
- After finding `q`, all points that lie on the line segment `pq` are also part of the hull and must be added.
- Add the new point(s) to the hull and set `p = q`.
- Repeat the process until the hull is closed, i.e., when the next point to be added is the starting point.

## Monotone Chain (Andrew's Algorithm)
This is a more efficient algorithm that builds the convex hull by constructing the upper and lower hulls separately. It first sorts all points by their x-coordinates (and y-coordinates for ties). Then, it iterates through the sorted points to build the lower hull, and then iterates in reverse to build the upper hull. This method is generally preferred for its efficiency and simpler implementation regarding collinear points.
**Time:** O(N log N), which is dominated by the initial sorting of the points. The two passes to build the upper and lower hulls each take O(N) time because each point is pushed onto and popped from the list at most once. · **Space:** O(N) to store the hull points. The lists for the lower and upper hulls can grow up to size N.
**Pros:** Efficient with a reliable O(N log N) time complexity.; Robust and generally easier to implement correctly than other hull algorithms like Graham Scan, especially when handling collinear points.; Avoids trigonometric functions and floating-point arithmetic, making it fast and precise.
**Cons:** The O(N log N) complexity is dominated by sorting, which might be suboptimal if the points have some pre-existing order or special distribution where a linear-time hull algorithm could apply (though this is rare).
### Explanation
The Monotone Chain algorithm, also known as Andrew's algorithm, is an efficient method for finding the convex hull of a set of points. Its main advantage is that it avoids explicit angle calculations and relies on the cross product to check orientation, which is less prone to floating-point errors and is computationally faster.

The algorithm works as follows:
1.  **Sort**: The first step is to sort all the points based on their x-coordinates. If two points have the same x-coordinate, they are sorted by their y-coordinate. This gives us an ordered sequence of points from left to right.
2.  **Build Hulls**: The algorithm then constructs the convex hull in two parts: the lower hull and the upper hull.
    *   **Lower Hull**: We iterate through the sorted points and build the lower hull. We use a list or stack to maintain the current lower hull vertices. For each point, we check if adding it maintains a counter-clockwise chain. If adding the new point creates a clockwise turn, it means the previous point is concave and not part of the hull, so we pop it. We continue this until a counter-clockwise turn is restored. Collinear points are kept, as the condition for popping is a strictly clockwise turn.
    *   **Upper Hull**: We do a similar pass, but this time from right to left (iterating through the sorted points in reverse), to construct the upper hull.
3.  **Combine**: The final convex hull is the union of the lower and upper hulls. The start and end points of the sorted list are part of both hulls, so we need to remove duplicates when combining them. A `HashSet` is an easy way to achieve this.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    // Helper function to calculate the cross product (orientation)
    // > 0 for counter-clockwise turn (left)
    // < 0 for clockwise turn (right)
    // = 0 for collinear points
    private int crossProduct(int[] p1, int[] p2, int[] p3) {
        return (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0]);
    }

    public int[][] outerTrees(int[][] trees) {
        if (trees.length <= 3) {
            return trees;
        }

        // Sort points lexicographically
        Arrays.sort(trees, (p1, p2) -> {
            if (p1[0] != p2[0]) {
                return p1[0] - p2[0];
            }
            return p1[1] - p2[1];
        });

        List<int[]> lowerHull = new ArrayList<>();
        // Build lower hull
        for (int[] point : trees) {
            while (lowerHull.size() >= 2 && crossProduct(lowerHull.get(lowerHull.size() - 2), lowerHull.get(lowerHull.size() - 1), point) < 0) {
                lowerHull.remove(lowerHull.size() - 1);
            }
            lowerHull.add(point);
        }

        List<int[]> upperHull = new ArrayList<>();
        // Build upper hull
        for (int i = trees.length - 1; i >= 0; i--) {
            int[] point = trees[i];
            while (upperHull.size() >= 2 && crossProduct(upperHull.get(upperHull.size() - 2), upperHull.get(upperHull.size() - 1), point) < 0) {
                upperHull.remove(upperHull.size() - 1);
            }
            upperHull.add(point);
        }

        // Combine hulls and remove duplicates
        Set<int[]> hull = new HashSet<>(lowerHull);
        hull.addAll(upperHull);

        return hull.toArray(new int[hull.size()][]);
    }
}
```
### Algorithm
- If there are 3 or fewer points, they all form the hull. Return them.
- Sort the input `trees` array lexicographically: first by x-coordinate, and then by y-coordinate for ties.
- Initialize an empty list, `hull`, to store the vertices of the hull.
- **Build the Lower Hull**: Iterate through the sorted points from left to right. For each point `p`, check if adding it to the `hull` would create a clockwise turn. A clockwise turn indicates that the last point added to the `hull` is not part of the lower hull and should be removed. We repeatedly pop from the `hull` as long as a clockwise turn is formed. Then, add the current point `p`.
- **Build the Upper Hull**: Iterate through the sorted points from right to left. Apply the same logic as for the lower hull: pop from the `hull` if a clockwise turn is formed, then add the current point.
- The first and last points of the sorted array are processed twice (once for each hull), but the final result should not contain duplicates. Using a `Set` to store the combined hull points handles this automatically.
- Convert the set of hull points back to an array and return it.

# Solutions
### Java

```java
class Solution {
public
  int[][] outerTrees(int[][] trees) {
    int n = trees.length;
    if (n < 4) {
      return trees;
    }
    Arrays.sort(
        trees, (a, b)->{ return a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]; });
    boolean[] vis = new boolean[n];
    int[] stk = new int[n + 10];
    int cnt = 1;
    for (int i = 1; i < n; ++i) {
      while (cnt > 1 &&
             cross(trees[stk[cnt - 1]], trees[stk[cnt - 2]], trees[i]) < 0) {
        vis[stk[--cnt]] = false;
      }
      vis[i] = true;
      stk[cnt++] = i;
    }
    int m = cnt;
    for (int i = n - 1; i >= 0; --i) {
      if (vis[i]) {
        continue;
      }
      while (cnt > m &&
             cross(trees[stk[cnt - 1]], trees[stk[cnt - 2]], trees[i]) < 0) {
        --cnt;
      }
      stk[cnt++] = i;
    }
    int[][] ans = new int[cnt - 1][2];
    for (int i = 0; i < ans.length; ++i) {
      ans[i] = trees[stk[i]];
    }
    return ans;
  }
private
  int cross(int[] a, int[] b, int[] c) {
    return (b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0]);
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> outerTrees(vector<vector<int>> &trees) {
    int n = trees.size();
    if (n < 4)
      return trees;
    sort(trees.begin(), trees.end());
    vector<int> vis(n);
    vector<int> stk(n + 10);
    int cnt = 1;
    for (int i = 1; i < n; ++i) {
      while (cnt > 1 &&
             cross(trees[stk[cnt - 1]], trees[stk[cnt - 2]], trees[i]) < 0)
        vis[stk[--cnt]] = false;
      vis[i] = true;
      stk[cnt++] = i;
    }
    int m = cnt;
    for (int i = n - 1; i >= 0; --i) {
      if (vis[i])
        continue;
      while (cnt > m &&
             cross(trees[stk[cnt - 1]], trees[stk[cnt - 2]], trees[i]) < 0)
        --cnt;
      stk[cnt++] = i;
    }
    vector<vector<int>> ans;
    for (int i = 0; i < cnt - 1; ++i)
      ans.push_back(trees[stk[i]]);
    return ans;
  }
  int cross(vector<int> &a, vector<int> &b, vector<int> &c) {
    return (b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0]);
  }
};

```

### Python

```python
class Solution:
    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]: def cross(i, j, k): a, b, c = trees[i], trees[j], trees[k] return (b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0]) n = len(trees) if n < 4: return trees trees . sort() vis = [False] * n stk = [0] for i in range(1, n): while len(stk) > 1 and cross(stk[- 2], stk[- 1], i) < 0: vis[stk . pop()] = False vis[i] = True stk . append(i) m = len(stk) for i in range(n - 2, - 1, - 1): if vis[i]: continue while len(stk) > m and cross(stk[- 2], stk[- 1], i) < 0: stk . pop() stk . append(i) stk . pop() return [trees[i] for i in stk]

```