Задача: 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, чтобы удалить дублирующиеся точки из стека.
Преобразуйте результат в массив и верните его.

😎 Решение:

var orientation = function(p, q, r) {
    return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]);
};

var outerTrees = function(points) {
    points.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);
    const hull = [];

    for (let point of points) {
        while (hull.length >= 2 && orientation(hull[hull.length - 2], hull[hull.length - 1], point) > 0) {
            hull.pop();
        }
        hull.push(point);
    }

    hull.pop();

    for (let i = points.length - 1; i >= 0; i--) {
        while (hull.length >= 2 && orientation(hull[hull.length - 2], hull[hull.length - 1], points[i]) > 0) {
            hull.pop();
        }
        hull.push(points[i]);
    }

    const uniqueHull = new Set(hull.map(JSON.stringify));
    return Array.from(uniqueHull).map(JSON.parse);
};

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