# 587. Erect the Fence

• Time: $O(n\log n)$
• 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; 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& 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 31 // 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 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 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]); } } 
  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 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))