You are given an array trees where trees[i] = [xi, yi] represents the location of a tree in the garden.

You are asked to 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.

&nbsp;
Example 1:

Input: points = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
Output: [[1,1],[2,0],[3,3],[2,4],[4,2]]


Example 2:

Input: points = [[1,2],[2,2],[4,2]]
Output: [[4,2],[2,2],[1,2]]


&nbsp;
Constraints:


	1 &lt;= points.length &lt;= 3000
	points[i].length == 2
	0 &lt;= xi, yi &lt;= 100
	All the given points are unique.


class Solution:

    """Compute the convex hull of a set of points.

        Use Andrew's Monotone Chain algorithm, which has order O(N log(N)),
        where N is the number of input points.
    """

    def cross(self, p, a, b):
        """Return the cross product of the vectors p -> a and p -> b."""
        return (a[0] - p[0]) * (b[1] - p[1]) \
            - (a[1] - p[1]) * (b[0] - p[0])

    def _convex_hull_monotone_chain(self, points):
        """Compute the convex hull of a list of points.
        
        Use Andrew's Monotone Chain algorithm, which is similar to Graham Scan,
        except that it doesn't require sorting the points by angle.  This algorithm
        takes O(N log(N)) time, where N is len(points).
        """
        # Ensure all points are unique, and sort lexicographically.
        points = list(sorted(set(points)))
        
        # If there are fewer than three points, they must form a hull.
        if len(points) <= 2:
            return points
        
        # Compute the lower and upper portion of the hull.
        lower, upper = [], []
        for out, it in ((lower, points), (upper, reversed(points))):
            for p in it:
                while len(out) >= 2 and self.cross(out[-2], out[-1], p) > 0:
                    out.pop()
                out.append(p)

        # Concatenate the upper and lower hulls.  Remove the last point from each
        # because those points are duplicated in both upper and lower.
        return lower[:-1] + upper[:-1]

    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:
        """
        Find the convex hull of a collection of points.
        Return a list of indices of points forming the hull in clockwise order,
        starting with the leftmost point.
        """
        # Convert input points to tuples.
        points = [tuple(p) for p in trees]
        ans = set()
        for point in self._convex_hull_monotone_chain(points):
            ans.add(point)
        return ans
class Solution {
     public static class Pair {
            int x;
            int y;
        
            Pair(int x, int y) {
              this.x = x;
              this.y = y;
            }
        
          }
    public int[][] outerTrees(int[][] trees) {
        List<Pair> points=new ArrayList<>();
        for(int[] point:trees){
           points.add(new Pair(point[0],point[1])); 
        }

        List<Pair> res=new ArrayList<>();
        if(points.size()==1){
            return trees;
        }
        int n=points.size();
        Collections.sort(points,(a,b)->a.y==b.y?a.x-b.x:a.y-b.y);
        HashSet<ArrayList<Integer>> dup=new HashSet<>();
        Stack<Pair> hull=new Stack<>();
        
        hull.push(points.get(0));
        hull.push(points.get(1));
        
        for(int i=2;i<n;i++){
            Pair top=hull.pop();
            while(!hull.isEmpty()&&ccw(hull.peek(),top,points.get(i))<0){
                top=hull.pop();
            }
            hull.push(top);
            hull.push(points.get(i));
        }
        for(int i=n-2;i>=0;i--){
            Pair top=hull.pop();
            while(!hull.isEmpty()&&ccw(hull.peek(),top,points.get(i))<0){
                top=hull.pop();
            }
            hull.push(top);
            hull.push(points.get(i));
        }

        for(Pair p:hull){
            ArrayList<Integer> tmp=new ArrayList<>();
            tmp.add(p.x);
            tmp.add(p.y);
            if(dup.contains(tmp))continue;
            dup.add(tmp);
            res.add(p);
        }

        int[][] ans=new int[res.size()][2];
        int i=0;
        for(Pair p:res){
            ans[i][0]=p.x;
            ans[i][1]=p.y;
            i++;
        }
        
        return ans;
        
    }

    public int ccw(Pair a,Pair b,Pair c){
        double cp=(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
        if(cp<0)return -1;
        else if(cp>0)return 1;
        else return 0;
    }
}
class Solution {
 public:
  vector<vector<int>> outerTrees(vector<vector<int>>& trees) {
    if (trees.size() <= 1) return trees;

    int origin = 0;
    for (int i = 0; i < trees.size(); ++i) {
      if (trees[origin][1] > trees[i][1] || trees[origin][1] == trees[i][1] && trees[origin][0] > trees[i][0]) {
        origin = i;
      }
    }
    swap(trees[0], trees[origin]);
    sort(trees.begin() + 1, trees.end(), [&](const vector<int>& lhs, const vector<int>& rhs) -> bool {
      int result = cross(trees[0], lhs, rhs);
      if (result != 0) return result > 0;
      return norm(trees[0], lhs) < norm(trees[0], rhs);
    });

    // deal with cases that the last k points are on one line
    int pos = trees.size() - 2;
    while (pos > 0 && cross(trees[0], trees.back(), trees[pos]) == 0) {
      --pos;
    }
    reverse(trees.begin() + pos + 1, trees.end());

    vector<vector<int>> ans = {trees[0], trees[1]};
    for (int i = 2; i < trees.size(); ++i) {
      int cross_result = cross(ans[ans.size() - 2], ans[ans.size() - 1], trees[i]);
      while (cross_result < 0) {
        ans.pop_back();
        cross_result = cross(ans[ans.size() - 2], ans[ans.size() - 1], trees[i]);
      }
      ans.push_back(trees[i]);
    }
    return ans;
  }

 private:
  inline double norm(const vector<int>& o, const vector<int>& x) {
    int xx = x[0] - o[0];
    int yy = x[1] - o[1];
    return sqrt(xx * xx + yy * yy);
  }

  inline int cross(const vector<int>& x, const vector<int>& y, const vector<int>& z) {
    return (y[0] - x[0]) * (z[1] - y[1]) - (y[1] - x[1]) * (z[0] - y[0]);
  }
};
const outerTrees = (trees) => {
    trees.sort((x, y) => {
        if (x[0] == y[0]) return x[1] - y[1];
        return x[0] - y[0];
    });
    let lower = [], upper = [];
    for (const tree of trees) {
        while (lower.length >= 2 && cmp(lower[lower.length - 2], lower[lower.length - 1], tree) > 0) lower.pop();
        while (upper.length >= 2 && cmp(upper[upper.length - 2], upper[upper.length - 1], tree) < 0) upper.pop();
        lower.push(tree);
        upper.push(tree);

    }
    return [...new Set(lower.concat(upper))];
};

const cmp = (p1, p2, p3) => {
    let [x1, y1] = p1;
    let [x2, y2] = p2;
    let [x3, y3] = p3;
    return (y3 - y2) * (x2 - x1) - (y2 - y1) * (x3 - x2);
};
Erect the Fence