# 587. Erect the Fence¶

• Time: $O(\texttt{sort})$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 // Monotone Chain class Solution { public: vector> outerTrees(vector>& trees) { vector> hull; ranges::sort(trees, [](const vector& a, const vector& b) { return a[0] == b[0] ? a[1] < b[1] : a[0] < b[0]; }); // Build the lower hull: left-to-right scan. for (const vector& 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 the 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 the redundant elements from the stack. ranges::sort(hull, [](const vector& a, const vector& b) { return a[0] == b[0] ? a[1] < b[1] : a[0] < b[0]; }); hull.erase(unique(hull.begin(), hull.end(), [](const vector& a, const vector& b) { return a[0] == b[0] && a[1] == b[1]; }), hull.end()); return hull; } private: int cross(const vector& p, const vector& q, const vector& r) { return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 // Monotone Chain class Solution { public int[][] outerTrees(int[][] trees) { Stack hull = new Stack<>(); Arrays.sort(trees, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]); // Build the 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 the 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 the redundant elements from the stack. return new HashSet<>(hull).stream().toArray(int[][] ::new); } 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]); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 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 the 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 the 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 the redundant elements from the stack. return list(set(hull))