leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0587.cpp (1113B)

0 class Solution { 1 using point_t = vector<int>; 2 3 public: 4 vector<point_t> outerTrees(vector<point_t> &trees) const { 5 const auto cross = [](const point_t &a, const point_t &b, const point_t &c) { 6 return (c[1] - a[1]) * (b[0] - a[0]) - (c[0] - a[0]) * (b[1] - a[1]); 7 }; 8 9 const auto cmp = [](const point_t &a, const point_t &b) { 10 return a[0] != b[0] ? a[0] < b[0] : a[1] < b[1]; 11 }; 12 13 const int n = size(trees); 14 vector<point_t> haul(2 * n); 15 int k = 0; 16 17 sort(begin(trees), end(trees), cmp); 18 19 for (int i = 0; i < n; i++) { 20 while (k >= 2 && cross(haul[k - 2], haul[k - 1], trees[i]) < 0) 21 k--; 22 haul[k++] = trees[i]; 23 } 24 25 for (int i = n - 2, t = k + 1; i >= 0; i--) { 26 while (k >= t && cross(haul[k - 2], haul[k - 1], trees[i]) < 0) 27 k--; 28 haul[k++] = trees[i]; 29 } 30 31 haul.resize(k); 32 sort(begin(haul), end(haul)); 33 haul.erase(unique(begin(haul), end(haul)), end(haul)); 34 35 return haul; 36 } 37 };