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