Задача: 587. Erect the Fence
Сложность: hard

Вам дан массив trees, где trees[i] = [xi, yi] представляет местоположение дерева в саду.
Оградите весь сад с использованием минимальной длины веревки, так как это дорого. Сад хорошо огорожен только в том случае, если все деревья окружены.
Верните координаты деревьев, которые находятся точно на периметре ограды. Вы можете вернуть ответ в любом порядке.

Пример:

Input: trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
Output: [[1,1],[2,0],[4,2],[3,3],[2,4]]
Explanation: All the trees will be on the perimeter of the fence except the tree at [2, 2], which will be inside the fence.

👨‍💻 Алгоритм:

1⃣ Сортировка точек и построение нижней оболочки:
Отсортируйте точки по их x-координатам, а в случае совпадения x-координат, по y-координатам.
Постройте нижнюю оболочку, добавляя точки к оболочке и удаляя последние точки, если они не образуют против часовой стрелки поворот.

2⃣ Построение верхней оболочки:
Пройдитесь по точкам в обратном порядке, чтобы построить верхнюю оболочку.
Добавляйте точки к оболочке и удаляйте последние точки, если они не образуют против часовой стрелки поворот.

3⃣ Удаление дублирующих элементов и возврат результата:
Используйте HashSet, чтобы удалить дублирующиеся точки из стека.
Преобразуйте результат в массив и верните его.

😎 Решение:

class Solution {
public:
    int orientation(vector<int>& p, vector<int>& q, vector<int>& r) {
        return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]);
    }

    vector<vector<int>> outerTrees(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), [](vector<int>& p, vector<int>& q) {
            return p[0] == q[0] ? p[1] < q[1] : p[0] < q[0];
        });

        vector<vector<int>> hull;

        for (auto& point : points) {
            while (hull.size() >= 2 && orientation(hull[hull.size() - 2], hull.back(), point) > 0)
                hull.pop_back();
            hull.push_back(point);
        }

        hull.pop_back();

        for (int i = points.size() - 1; i >= 0; --i) {
            while (hull.size() >= 2 && orientation(hull[hull.size() - 2], hull.back(), points[i]) > 0)
                hull.pop_back();
            hull.push_back(points[i]);
        }

        set<vector<int>> s(hull.begin(), hull.end());
        return vector<vector<int>>(s.begin(), s.end());
    }
};

Ставь 👍 и забирай 📚 Базу знаний