Erect the Fence LeetCode solution in C++

1
class Solution {
2
 public:
3
  vector<vector<int>> outerTrees(vector<vector<int>> &trees) {
4
    if (trees.size() <= 1) return trees;
5

6
    int origin = 0;
7
    for (int i = 0; i < trees.size(); ++i) {
8
      if (trees[origin][1] > trees[i][1] ||
9
          trees[origin][1] == trees[i][1] && trees[origin][0] > trees[i][0]) {
10
        origin = i;
11
      }
12
    }
13
    swap(trees[0], trees[origin]);
14
    sort(trees.begin() + 1, trees.end(),
15
         [&](const vector<int> &lhs, const vector<int> &rhs) -> bool {
16
           int result = cross(trees[0], lhs, rhs);
17
           if (result != 0) return result > 0;
18
           return norm(trees[0], lhs) < norm(trees[0], rhs);
19
         });
20

21
    // deal with cases that the last k points are on one line
22
    int pos = trees.size() - 2;
23
    while (pos > 0 && cross(trees[0], trees.back(), trees[pos]) == 0) {
24
      --pos;
25
    }
26
    reverse(trees.begin() + pos + 1, trees.end());
27

28
    vector<vector<int>> ans = {trees[0], trees[1]};
29
    for (int i = 2; i < trees.size(); ++i) {
30
      int cross_result = cross(ans[ans.size() - 2], ans[ans.size() - 1], trees[i]);
31
      while (cross_result < 0) {
32
        ans.pop_back();
33
        cross_result = cross(ans[ans.size() - 2], ans[ans.size() - 1], trees[i]);
34
      }
35
      ans.push_back(trees[i]);
36
    }
37
    return ans;
38
  }
39

40
 private:
41
  inline double norm(const vector<int> &o, const vector<int> &x) {
42
    int xx = x[0] - o[0];
43
    int yy = x[1] - o[1];
44
    return sqrt(xx * xx + yy * yy);
45
  }
46

47
  inline int cross(const vector<int> &x, const vector<int> &y, const vector<int> &z) {
48
    return (y[0] - x[0]) * (z[1] - y[1]) - (y[1] - x[1]) * (z[0] - y[0]);
49
  }
50
};