leetcode

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 };