Algorithm (Convex Hull)

1. This is a model problem for finding convex hull. We will use the classcial Graham Scan algorithm.
2. Let’s denote the input points by $P.$ The Graham Scan Algorithm could be described as follows:
   1. Construct a record type state of the following three states:
      1. A partition $P$ of two sets, $p_{\mathrm{init}}$ and $P_{\mathrm{other}}=P-p_{\mathrm{init}}$ where $p_{\mathrm{init}}$ is the most buttom left point of $P$.
      2. A stack of points, which we denote as $\mathrm{STACK}.$
   2. For initial state, we have $\mathrm{STACK}=\{p_{\mathrm{init}},P_{\mathrm{other}}[0]\}$ and that $P_{\mathrm{other}}$ are sorted by polar angles with $p_{\text{init}}.$
   3. For every points in $P_{\mathrm{other}}[1:\mathrm{end}]$, we add push it to $\mathrm{STACK}$ and maintain the following invariant: at any moment, all points in $\mathrm{STACK}$ are on the boundary of the convex hull of $P$. To do so, we could use cross product to check if any points in $\mathrm{STACK}$ lies inside the convex hull. For more details on cross product, please consult any entry level linear algebra textbook.

Code (Cpp17)

class Solution {
  public:
  vector<vector<int>> outerTrees(vector<vector<int>>& points) {
    static constexpr double PI = std::atan(1) * 4;
    static constexpr double EPS = 1e-8;

    using point_t = std::vector<int>;

    struct point_info_t {
      point_t point;
      double angle;
      double distance;
    };

    struct state_t {
      mutable point_t initial_point;
      mutable std::vector<point_info_t> other_points;
      mutable std::deque<point_t> DQ;
    };

    auto dist = [&](const point_t& p1, const point_t& p2) {
      const auto dx = p1[0] - p2[0];
      const auto dy = p1[1] - p2[1];
      return dx * dx + dy * dy;
    };

    auto polar_angle = [&](const point_t& p1, const point_t& p2) {
      const auto ans = 180.0 * (std::atan((double(p1[1]) - double(p2[1])) / (double(p1[0]) - double(p2[0])))) / PI;
      return ans >= 0 ? ans : 180 + ans;
    };

    auto cross_product = [&](const auto& v1, const auto& v2) {
      const auto [v1_p1, v1_p2] = v1;
      const auto [v2_p1, v2_p2] = v2;
      const auto [x1, y1]       = pair(v1_p1[0] - v1_p2[0], v1_p1[1] - v1_p2[1]);
      const auto [x2, y2]       = pair(v2_p1[0] - v2_p2[0], v2_p1[1] - v2_p2[1]);
      return x1 * y2 - x2 * y1;
    };

    auto ccw = [&](const point_t& p1, const point_t& p2, const point_t& p3) {
      return cross_product(std::pair(p2, p3), std::pair(p1, p3)) >= 0;
    };

    auto ensure_state_invariant = [&](state_t* state) {
      auto& [initial_point, other_points, DQ] = *state;
      while (std::size(DQ) >= 3 and not ccw(DQ[0], DQ[1], DQ[2])) {
        auto x = DQ.front(); DQ.pop_front();
        auto y = DQ.front(); DQ.pop_front();
        DQ.emplace_front(x);
      }
    };

    auto prepare_initial_state = [&, points]() mutable {
      // sort by lexicographical order first
      std::sort(std::begin(points), std::end(points), [&](const auto& x, const auto& y) {
        if (x[1] == y[1])
          return x[0] < y[0];
        else
          return x[1] < y[1];
      });
      // take the buttom left point as the starting point
      const auto initial_point = point_t{points.front()[0], points.front()[1]};
      // other points are sorted by polar angle first and by distance second.
      const auto other_points  = [&](std::vector<point_info_t> self = {}) {
        std::transform(std::begin(points) + 1, std::end(points), std::back_inserter(self), [&](const auto& x) {
          return point_info_t{x, polar_angle(x, initial_point), dist(x, initial_point)};
        });
        if (std::size(self) < 1)
          return self;
        else {
          const auto min_angle = (*min_element(std::begin(self), std::end(self), [&](const auto &x, const auto &y) {
            return x.angle < y.angle;
          })).angle;
          std::sort(std::begin(self), std::end(self), [&](const auto& x, const auto& y) {
            if (std::abs(x.angle - y.angle) < EPS) {
              // special case when the starting segment is a vertical line
              if (std::abs(min_angle - 90) < EPS and std::max(std::abs(x.angle - 90.0), std::abs(y.angle - 90.0)) < EPS)
                return x.distance < y.distance;
              // on the left hand side
              else if (std::min(x.angle, y.angle) >= 90 - EPS)
                return x.distance > y.distance;
              // on the right hand side
              else
                return x.distance < y.distance;
            }
            else
              return x.angle < y.angle;
          });
          return self;
        }
      }();

      const auto DQ = [&](std::deque<point_t> self = {}) {
        self.emplace_front(initial_point);
        if (std::size(other_points) > 0)
          self.emplace_front(other_points[0].point);
        return self;
      }();
      return state_t{initial_point, other_points, DQ};
    };

    const auto solution = [&](std::vector<point_t> self = {}) {
      auto state = prepare_initial_state();
      for (int i = 1; i < std::size(state.other_points); ++i) {
        state.DQ.emplace_front(state.other_points[i].point);
        ensure_state_invariant(&state);
      }
      return std::vector<point_t>(std::begin(state.DQ), std::end(state.DQ));
    }();

    return solution;
    ;
  }
};