Erect the Fence
Problem
Given tree coordinates, return the points lying on the convex hull (the perimeter of the rope around all trees, including collinear ones).
trees=[[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]][[1,1],[2,0],[4,2],[3,3],[2,4]]def outer_trees(trees):
trees.sort()
def cross(o, a, b): return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])
lower, upper = [], []
for p in trees:
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) < 0: lower.pop()
lower.append(p)
for p in reversed(trees):
while len(upper) >= 2 and cross(upper[-2], upper[-1], p) < 0: upper.pop()
upper.append(p)
return list({tuple(p) for p in lower + upper})function outerTrees(trees) {
trees.sort((a, b) => a[0]-b[0] || a[1]-b[1]);
const cross = (o, a, b) => (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0]);
const lower = [], upper = [];
for (const p of trees) {
while (lower.length >= 2 && cross(lower[lower.length-2], lower[lower.length-1], p) < 0) lower.pop();
lower.push(p);
}
for (let i = trees.length - 1; i >= 0; i--) {
const p = trees[i];
while (upper.length >= 2 && cross(upper[upper.length-2], upper[upper.length-1], p) < 0) upper.pop();
upper.push(p);
}
return [...new Set([...lower, ...upper].map(p => p.join(',')))].map(s => s.split(',').map(Number));
}int[][] outerTrees(int[][] trees) {
Arrays.sort(trees, (a, b) -> a[0] != b[0] ? a[0]-b[0] : a[1]-b[1]);
Deque lower = new ArrayDeque<>(), upper = new ArrayDeque<>();
for (int[] p : trees) {
while (lower.size() >= 2 && cross(secondLast(lower), lower.peek(), p) < 0) lower.pop();
lower.push(p);
}
for (int i = trees.length - 1; i >= 0; i--) {
int[] p = trees[i];
while (upper.size() >= 2 && cross(secondLast(upper), upper.peek(), p) < 0) upper.pop();
upper.push(p);
}
Set seen = new HashSet<>();
List out = new ArrayList<>();
for (int[] p : lower) if (seen.add(p[0]+","+p[1])) out.add(p);
for (int[] p : upper) if (seen.add(p[0]+","+p[1])) out.add(p);
return out.toArray(new int[0][]);
} int cross(vector& o, vector& a, vector& b) {
return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0]);
}
vector> outerTrees(vector>& trees) {
sort(trees.begin(), trees.end());
vector> lo, up;
for (auto& p : trees) {
while (lo.size() >= 2 && cross(lo[lo.size()-2], lo.back(), p) < 0) lo.pop_back();
lo.push_back(p);
}
for (int i = trees.size()-1; i >= 0; i--) {
auto& p = trees[i];
while (up.size() >= 2 && cross(up[up.size()-2], up.back(), p) < 0) up.pop_back();
up.push_back(p);
}
set> s(lo.begin(), lo.end()); s.insert(up.begin(), up.end());
return {s.begin(), s.end()};
} Explanation
This finds the convex hull — the tightest rope that wraps around all the trees — using Andrew's monotone chain algorithm. The hull is built in two halves: a lower boundary and an upper boundary.
First we sort the points left to right (and bottom to top for ties). Then we sweep through them building the lower chain, and sweep back through them building the upper chain. Joining the two halves gives the full outline.
The heart is the cross product. For three points o, a, b it tells us whether the turn is left or right. While the last three points make a clockwise (right) turn (cross < 0), the middle point is inside the hull, so we pop it off. Keeping only left turns traces the outer boundary.
Using < 0 (instead of <= 0) keeps points that lie exactly on an edge, which this problem wants. At the end we union the lower and upper chains and drop duplicates.
Example: with the six trees, sorting then sweeping builds the lower path (1,1)→(2,0)→(4,2) and the upper path back through (3,3)→(2,4), giving the 5 hull vertices.