Here, We see Erect the Fence LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
Erect the Fence LeetCode Solution
Table of Contents
Problem Statement
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:
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.
Erect the Fence LeetCode Solution C++
class Solution {
public:
int Cross_Product_fun(vector<int> p,vector<int> q,vector<int> r){
int ans = ((q[0]-p[0])*(r[1]-p[1]))-((q[1]-p[1])*(r[0]-p[0]));
return ans;
}
vector<vector<int>> outerTrees(vector<vector<int>>& trees) {
int sz = trees.size();
if(sz<=3){
return trees;
}
else{
sort(trees.begin(),trees.end());
vector<vector<int>> up_hull;
vector<vector<int>> low_hull;
up_hull.push_back(trees[0]);
up_hull.push_back(trees[1]);
for(int j=2;j<sz;j++){
int n = up_hull.size();
while(n>=2 && Cross_Product_fun(up_hull[n-2],up_hull[n-1],trees[j]) > 0){
up_hull.pop_back();
n--;
}
up_hull.push_back(trees[j]);
}
low_hull.push_back(trees[sz-1]);
low_hull.push_back(trees[sz-2]);
for(int j=sz-3;j>=0;j--){
int m = low_hull.size();
while(m>=2 && Cross_Product_fun(low_hull[m-2],low_hull[m-1],trees[j]) > 0){
low_hull.pop_back();
m--;
}
low_hull.push_back(trees[j]);
}
up_hull.insert(up_hull.end(),low_hull.begin(),low_hull.end());
sort(up_hull.begin(),up_hull.end());
up_hull.erase(unique(up_hull.begin(),up_hull.end()),up_hull.end());
return up_hull;
}
}
};Code language: PHP (php)Erect the Fence LeetCode Solution Java
class Solution {
public int[][] outerTrees(int[][] trees) {
Arrays.sort(trees, (p1, p2) -> {
if (p1[0] == p2[0]) {
return p2[1] - p1[1];
}
return p1[0] - p2[0];
});
Set<Point> res = new HashSet<>();
res.add(new Point(trees[0]));
int n = trees.length;
int i = 0;
while (i != n - 1) {
double bestSlope = Integer.MIN_VALUE;
int[] nextPoint = trees[i + 1];
int jCandidate = i + 1;
for (int j = i + 1; j < n; j++) {
double slope = calculateSlope(trees[i], trees[j]);
if (slope > bestSlope) {
bestSlope = slope;
nextPoint = trees[j];
jCandidate = j;
}
}
i = jCandidate;
res.add(new Point(nextPoint));
}
i = n - 1;
while (i != 0) {
double bestSlope = Integer.MIN_VALUE;
int[] nextPoint = trees[i - 1];
int jCandidate = i - 1;
for (int j = i - 1; j >= 0; j--) {
double slope = calculateSlope(trees[j], trees[i]);
if (slope > bestSlope) {
bestSlope = slope;
nextPoint = trees[j];
jCandidate = j;
}
}
i = jCandidate;
res.add(new Point(nextPoint));
}
return res.stream().map(p -> new int[]{p.x, p.y}).toArray(int[][]::new);
}
private double calculateSlope(int[] p1, int[] p2) {
if (p1[0] == p2[0]) { // 0 division
return Integer.MIN_VALUE;
}
return (double) (p2[1] - p1[1]) / (double) (p2[0] - p1[0]);
}
private static class Point {
public int x;
public int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public Point(int[] p) {
this.x = p[0];
this.y = p[1];
}
public String toString() {
return "Point{" +
"x=" + x +
", y=" + y +
'}';
}
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Point point = (Point) o;
return x == point.x && y == point.y;
}
public int hashCode() {
return Objects.hash(x, y);
}
}
}Code language: PHP (php)Erect the Fence Solution JavaScript
var outerTrees = function(trees) {
trees.sort((a, b) => a[0] - b[0] == 0 ? a[1] - b[1] : a[0] - b[0])
const cmpSlopes = ([x1, y1], [x2, y2], [x3, y3]) => (y3 - y1) * (x2 - x1) - (y2 - y1) * (x3 - x1)
const higher = []
const lower = []
for (let point of trees) {
while (higher.length > 1 && cmpSlopes(higher[higher.length - 2], higher[higher.length - 1], point) > 0)
higher.pop();
while (lower.length > 1 && cmpSlopes(lower[lower.length - 2], lower[lower.length - 1], point) < 0)
lower.pop();
higher.push(point);
lower.push(point);
}
return [...new Set([...higher, ...lower])];
};Code language: JavaScript (javascript)Erect the Fence Solution Python
class Solution(object):
def outerTrees(self, trees):
def ccw(A, B, C):
return (B[0]-A[0])*(C[1]-A[1]) - (B[1]-A[1])*(C[0]-A[0])
if len(trees) <= 1:
return trees
hull = []
trees.sort()
for i in itertools.chain(range(len(trees)), reversed(range(len(trees)-1))):
while len(hull) >= 2 and ccw(hull[-2], hull[-1], trees[i]) < 0:
hull.pop()
hull.append(trees[i])
hull.pop()
for i in range(1, (len(hull)+1)//2):
if hull[i] != hull[-1]:
break
hull.pop()
return hullCode language: HTML, XML (xml)