Что решает
оболочки
Статьи
GEO
Алгоритм
Выпуклая оболочка
Наименьший выпуклый многоугольник, содержащий все точки, за O(n log n).
O(n log n)
2 задачи
GEO
Приём
Вращающиеся калиперы
У 971 из 2679 кварталов центра Алматы наименьший прямоугольник повёрнут на 4–8°: сетка улиц смотрит не строго на север.
O(n) после оболочки, O(n log n) с ней
2 задачи
Задачи
Часто рядом
точки на плоскости 2 многоугольник 2 сортировка 1 стек 1 геоданные 1 наука и физика 1 классика 1 олимпиады 1 оптимизация 1 два указателя 1 карты и навигация 1