Erect the Fence

Problem Statement

In the provided scenario, an array named trees is given where each element trees[i] = [xi, yi] corresponds to the Cartesian coordinates of a tree situated in a garden. The primary task revolves around constructing a boundary or fence using the least possible length of rope so that every tree within trees is encompassed by this boundary. Only the trees that lie exactly on the perimeter of this boundary should be returned, and the sequence of their coordinates can be in any arbitrary order. This exercise challenges us to define and extract the outer contour of a cluster of points on a 2D plane.

Examples

Example 1

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

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.

Approach and Intuition

1. Given the problem is about enclosing trees (or points) within the minimal rope length, this is a classic computational geometry problem known as computing the "Convex Hull" of a set of points. The convex hull is the smallest convex boundary that can encompass all given points (trees in our case).

   • If you imagine stretching a rubber band around all the points and then releasing it, the shape formed by the rubber band is analogous to the convex hull.

2. From the examples:

   • Example 1:

     • Input: trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
     • The output [1,1],[2,0],[4,2],[3,3],[2,4] represents the points on the perimeter of the convex hull. The tree at [2, 2] is not on the perimeter, signifying it lies strictly inside the hull.

   • Example 2:

     • Input: trees = [[1,2],[2,2],[4,2]]
     • The output shows all points returned [4,2],[2,2],[1,2]. This is because all the points here are collinear, forming a straight line which is in itself the convex hull.

3. Algorithmically, Convex Hull problems can be solved using different approaches such as:

   • Graham's scan
   • Andrew's monotone chain algorithm
   • Quickhull
   • These algorithms typically operate in O(n log n) time complexity, where n is the number of points (trees).

4. Since the task involved returning points on the convex hull, these algorithms would effectively identify boundary trees by assessing angular relationships between points and determining if an inclusion of a point would result in a continued convex shape.

5. Considering the constraints, where the number of trees can go up to 3000 and all positions are guaranteed unique, an O(n log n) solution is computationally feasible.

This analysis suggests that by programmatically determining the convex hull of a given set of points representing trees, one can discern the minimum-length perimeter that encloses all points and subsequently identify which trees lie exactly on this perimeter.

Solutions

public class Solution {
    public int calcOrientation(int[] point1, int[] point2, int[] point3) {
        return (point2[1] - point1[1]) * (point3[0] - point2[0]) - (point2[0] - point1[0]) * (point3[1] - point2[1]);
    }
    public int[][] outerTrees(int[][] trees) {
        Arrays.sort(trees, new Comparator<int[]> () {
            public int compare(int[] tree1, int[] tree2) {
                return tree2[0] - tree1[0] == 0 ? tree2[1] - tree1[1] : tree2[0] - tree1[0];
            }
        });
        Stack<int[]> convexHull = new Stack<>();
        for (int i = 0; i < trees.length; i++) {
            while (convexHull.size() >= 2 && calcOrientation(convexHull.get(convexHull.size() - 2), convexHull.get(convexHull.size() - 1), trees[i]) > 0)
                convexHull.pop();
            convexHull.push(trees[i]);
        }
        convexHull.pop();
        for (int i = trees.length - 1; i >= 0; i--) {
            while (convexHull.size() >= 2 && calcOrientation(convexHull.get(convexHull.size() - 2), convexHull.get(convexHull.size() - 1), trees[i]) > 0)
                convexHull.pop();
            convexHull.push(trees[i]);
        }
        HashSet<int[]> resultSet = new HashSet<>(convexHull);
        return resultSet.toArray(new int[resultSet.size()][]);
    }
}