leetcode

commit 6f2d874f429bc33d870af050cd2d8bfd82a5b82e
parent 7eb221874b996f34ef2038e5a61f53bcf613e768
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri,  6 Dec 2024 15:45:24 +0100

1 Random Problem

Diffstat:
A
Problems/0587.cpp
 | 
38
++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 39 insertions(+), 0 deletions(-)
diff --git a/Problems/0587.cpp b/Problems/0587.cpp
@@ -0,0 +1,38 @@
+class Solution {
+    using point_t = vector<int>;
+
+  public:
+    vector<point_t> outerTrees(vector<point_t> &trees) const {
+        const auto cross = [](const point_t &a, const point_t &b, const point_t &c) {
+            return (c[1] - a[1]) * (b[0] - a[0]) - (c[0] - a[0]) * (b[1] - a[1]);
+        };
+
+        const auto cmp = [](const point_t &a, const point_t &b) {
+            return a[0] != b[0] ? a[0] < b[0] : a[1] < b[1];
+        };
+
+        const int n = size(trees);
+        vector<point_t> haul(2 * n);
+        int k = 0;
+
+        sort(begin(trees), end(trees), cmp);
+
+        for (int i = 0; i < n; i++) {
+            while (k >= 2 && cross(haul[k - 2], haul[k - 1], trees[i]) < 0)
+                k--;
+            haul[k++] = trees[i];
+        }
+
+        for (int i = n - 2, t = k + 1; i >= 0; i--) {
+            while (k >= t && cross(haul[k - 2], haul[k - 1], trees[i]) < 0)
+                k--;
+            haul[k++] = trees[i];
+        }
+
+        haul.resize(k);
+        sort(begin(haul), end(haul));
+        haul.erase(unique(begin(haul), end(haul)), end(haul));
+
+        return haul;
+    }
+};
diff --git a/README.md b/README.md
@@ -471,6 +471,7 @@ reference and a base for solving problems.
 |  0584  |    Easy    | [Find Customer Referee](Problems/0584.cpp)                                                         |
 |  0585  |   Medium   | [Investments in 2016](Problems/0585.cpp)                                                           |
 |  0586  |    Easy    | [Customer Placing the Largest Number of Orders](Problems/0586.cpp)                                 |
+|  0587  |    Hard    | [Erect the Fence](Problems/0587.cpp)                                                               |
 |  0589  |    Easy    | [N-ary Tree Preorder Traversal](Problems/0589.cpp)                                                 |
 |  0590  |    Easy    | [N-ary Tree Postorder Traversal](Problems/0590.cpp)                                                |
 |  0592  |   Medium   | [Fraction Addition and Subtraction](Problems/0592.cpp)                                             |