Table of Contents

# Erect the Fence – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

You are given an array `trees`

where `trees[i] = [x`

represents the location of a tree in the garden._{i}, y_{i}]

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*.

**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]]

**Constraints:**

`1 <= points.length <= 3000`

`points[i].length == 2`

`0 <= x`

_{i}, y_{i}<= 100- All the given points are
**unique**.

# C++ Erect the Fence LeetCode Solution

```
``````
class Solution {
public:
typedef int coord_t; // coordinate type
typedef long long coord2_t; // must be big enough to hold 2*max(|coordinate|)^2
// 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross
// product. Returns a positive value, if OAB makes a counter-clockwise turn,
// negative for clockwise turn, and zero if the points are collinear.
coord2_t cross(const Point &O, const Point &A, const Point &B) {
return (A.x - O.x) * (coord2_t)(B.y - O.y) -
(A.y - O.y) * (coord2_t)(B.x - O.x);
}
static bool cmp(Point &p1, Point &p2) {
return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);
}
static bool equ(Point &p1, Point &p2) { return p1.x == p2.x && p1.y == p2.y; }
// Returns a list of points on the convex hull in counter-clockwise order.
// Note: the last point in the returned list is the same as the first one.
vector<Point> outerTrees(vector<Point> &P) {
int n = P.size(), k = 0;
vector<Point> H(2 * n);
// Sort points lexicographically
sort(P.begin(), P.end(), cmp);
// Build lower hull
for (int i = 0; i < n; i++) {
while (k >= 2 && cross(H[k - 2], H[k - 1], P[i]) < 0) k--;
H[k++] = P[i];
}
// Build upper hull
for (int i = n - 2, t = k + 1; i >= 0; i--) {
while (k >= t && cross(H[k - 2], H[k - 1], P[i]) < 0) k--;
H[k++] = P[i];
}
// Remove duplicates
H.resize(k);
sort(H.begin(), H.end(), cmp);
H.erase(unique(H.begin(), H.end(), equ), H.end());
return H;
}
};
```

# Java Erect the Fence LeetCode Solution

```
``````
public class Solution {
public List<Point> outerTrees(Point[] points) {
if (points.length <= 1)
return Arrays.asList(points);
sortByPolar(points, bottomLeft(points));
Stack<Point> stack = new Stack<>();
stack.push(points[0]);
stack.push(points[1]);
for (int i = 2; i < points.length; i++) {
Point top = stack.pop();
while (ccw(stack.peek(), top, points[i]) < 0)
top = stack.pop();
stack.push(top);
stack.push(points[i]);
}
return new ArrayList<>(stack);
}
private static Point bottomLeft(Point[] points) {
Point bottomLeft = points[0];
for (Point p : points)
if (p.y < bottomLeft.y || p.y == bottomLeft.y && p.x < bottomLeft.x)
bottomLeft = p;
return bottomLeft;
}
/**
* @return positive if counter-clockwise, negative if clockwise, 0 if collinear
*/
private static int ccw(Point a, Point b, Point c) {
return a.x * b.y - a.y * b.x + b.x * c.y - b.y * c.x + c.x * a.y - c.y * a.x;
}
/**
* @return distance square of |p - q|
*/
private static int dist(Point p, Point q) {
return (p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y);
}
private static void sortByPolar(Point[] points, Point r) {
Arrays.sort(points, (p, q) -> {
int compPolar = ccw(p, r, q);
int compDist = dist(p, r) - dist(q, r);
return compPolar == 0 ? compDist : compPolar;
});
// find collinear points in the end positions
Point p = points[0], q = points[points.length - 1];
int i = points.length - 2;
while (i >= 0 && ccw(p, q, points[i]) == 0)
i--;
// reverse sort order of collinear points in the end positions
for (int l = i + 1, h = points.length - 1; l < h; l++, h--) {
Point tmp = points[l];
points[l] = points[h];
points[h] = tmp;
}
}
}
```

# Python 3 Erect the Fence LeetCode Solution

```
``````
class Solution(object):
def outerTrees(self, points):
"""Computes the convex hull of a set of 2D points.
Input: an iterable sequence of (x, y) pairs representing the points.
Output: a list of vertices of the convex hull in counter-clockwise order,
starting from the vertex with the lexicographically smallest coordinates.
Implements Andrew's monotone chain algorithm. O(n log n) complexity.
"""
# Sort the points lexicographically (tuples are compared lexicographically).
# Remove duplicates to detect the case we have just one unique point.
# points = sorted(set(points))
points = sorted(points, key=lambda p: (p.x, p.y))
# Boring case: no points or a single point, possibly repeated multiple times.
if len(points) <= 1:
return points
# 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
# Returns a positive value, if OAB makes a counter-clockwise turn,
# negative for clockwise turn, and zero if the points are collinear.
def cross(o, a, b):
# return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)
# Build lower hull
lower = []
for p in points:
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) < 0:
lower.pop()
lower.append(p)
# Build upper hull
upper = []
for p in reversed(points):
while len(upper) >= 2 and cross(upper[-2], upper[-1], p) < 0:
upper.pop()
upper.append(p)
# Concatenation of the lower and upper hulls gives the convex hull.
# Last point of each list is omitted because it is repeated at the
# beginning of the other list.
# return lower[:-1] + upper[:-1]
return list(set(lower[:-1] + upper[:-1]))
```

Array-1180

String-562

Hash Table-412

Dynamic Programming-390

Math-368

Sorting-264

Greedy-257

Depth-First Search-256

Database-215

Breadth-First Search-200

Tree-195

Binary Search-191

Matrix-176

Binary Tree-160

Two Pointers-151

Bit Manipulation-140

Stack-133

Heap (Priority Queue)-117

Design-116

Graph-108

Simulation-103

Prefix Sum-96

Backtracking-92

Counting-86

Sliding Window-73

Linked List-69

Union Find-66

Ordered Set-48

Monotonic Stack-47

Recursion-43

Trie-41

Binary Search Tree-40

Divide and Conquer-40

Enumeration-39

Bitmask-37

Queue-33

Memoization-32

Topological Sort-31

Geometry-30

Segment Tree-27

Game Theory-24

Hash Function-24

Binary Indexed Tree-21

Interactive-18

Data Stream-17

String Matching-17

Rolling Hash-17

Shortest Path-16

Number Theory-16

Combinatorics-15

Randomized-12

Monotonic Queue-9

Iterator-9

Merge Sort-9

Concurrency-9

Doubly-Linked List-8

Brainteaser-8

Probability and Statistics-7

Quickselect-7

Bucket Sort-6

Suffix Array-6

Minimum Spanning Tree-5

Counting Sort-5

Shell-4

Line Sweep-4

Reservoir Sampling-4

Eulerian Circuit-3

Radix Sort-3

Strongly Connected Componen-t2

Rejection Sampling-2

Biconnected Component-1