## Erect the Fence

• Time:O(n\log n)
• Space:O(n)

## C++

// Monotone Chain
class Solution {
public:
vector<vector<int>> outerTrees(vector<vector<int>>& trees) {
vector<vector<int>> hull;

sort(begin(trees), end(trees), [](const auto& a, const auto& b) {
return a[0] == b[0] ? a[1] < b[1] : a[0] < b[0];
});

// Build lower hull: left-to-right scan
for (const auto& tree : trees) {
while (hull.size() > 1 &&
cross(hull.back(), hull[hull.size() - 2], tree) > 0)
hull.pop_back();
hull.push_back(tree);
}
hull.pop_back();

// Build upper hull: right-to-left scan
for (int i = trees.size() - 1; i >= 0; --i) {
while (hull.size() > 1 &&
cross(hull.back(), hull[hull.size() - 2], trees[i]) > 0)
hull.pop_back();
hull.push_back(trees[i]);
}

// Remove redundant elements from the stack
sort(begin(hull), end(hull), [](const auto& a, const auto& b) {
return a[0] == b[0] ? a[1] < b[1] : a[0] < b[0];
});
hull.erase(
unique(begin(hull), end(hull),
[](const auto& a,
const auto& b) { return a[0] == b[0] && a[1] == b[1]; }),
end(hull));
return hull;
}

private:
int cross(const vector<int>& p, const vector<int>& q, const vector<int>& r) {
return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]);
}
};

## JAVA

// Monotone Chain
class Solution {
public int[][] outerTrees(int[][] trees) {
Stack<int[]> hull = new Stack<>();

Arrays.sort(trees, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);

// Build lower hull: left-to-right scan
for (int[] tree : trees) {
while (hull.size() > 1 && cross(hull.peek(), hull.get(hull.size() - 2), tree) > 0)
hull.pop();
hull.push(tree);
}
hull.pop();

// Build upper hull: right-to-left scan
for (int i = trees.length - 1; i >= 0; --i) {
while (hull.size() > 1 && cross(hull.peek(), hull.get(hull.size() - 2), trees[i]) > 0)
hull.pop();
hull.push(trees[i]);
}

// Remove redundant elements from the stack
HashSet<int[]> unique = new HashSet<>(hull);
return unique.toArray(new int[unique.size()][]);
}

private int cross(int[] p, int[] q, int[] r) {
return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]);
}
}

## Python

class Solution:
def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:
hull = []

trees.sort(key=lambda x: (x[0], x[1]))

def cross(p: List[int], q: List[int], r: List[int]) -> int:
return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])

# Build lower hull: left-to-right scan
for tree in trees:
while len(hull) > 1 and cross(hull[-1], hull[-2], tree) > 0:
hull.pop()
hull.append(tuple(tree))
hull.pop()

# Build upper hull: right-to-left scan
for tree in reversed(trees):
while len(hull) > 1 and cross(hull[-1], hull[-2], tree) > 0:
hull.pop()
hull.append(tuple(tree))

# Remove redundant elements from the stack
return list(set(hull))