Задача: 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 {
    private function orientation($p, $q, $r) {
        return ($q[1] - $p[1]) * ($r[0] - $q[0]) - ($q[0] - $p[0]) * ($r[1] - $q[1]);
    }

    function outerTrees($points) {
        usort($points, function($a, $b) {
            return $a[0] === $b[0] ? $a[1] - $b[1] : $a[0] - $b[0];
        });

        $hull = [];

        foreach ($points as $point) {
            while (count($hull) >= 2 && $this->orientation($hull[count($hull) - 2], $hull[count($hull) - 1], $point) > 0) {
                array_pop($hull);
            }
            $hull[] = $point;
        }

        array_pop($hull);

        for ($i = count($points) - 1; $i >= 0; $i--) {
            while (count($hull) >= 2 && $this->orientation($hull[count($hull) - 2], $hull[count($hull) - 1], $points[$i]) > 0) {
                array_pop($hull);
            }
            $hull[] = $points[$i];
        }

        $uniqueHull = [];
        foreach ($hull as $h) {
            $uniqueHull[implode(',', $h)] = $h;
        }

        return array_values($uniqueHull);
    }
}

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