Задачник Базовый курс EN

На чём держится

многоугольник

Статьи

GEO Приём Векторы и ориентация Знак векторного произведения — поворот налево или направо; на нём стоит почти вся вычислительная геометрия. O(1) на один поворот 2 задачи GEO Алгоритм Выпуклая оболочка Наименьший выпуклый многоугольник, содержащий все точки, за O(n log n). O(n log n) 2 задачи GEO Алгоритм Точка в многоугольнике Луч из точки пересекает границу нечётное число раз — точка внутри; число оборотов — то же со знаками. O(n) на точку 2 задачи GEO Алгоритм Площадь многоугольника Площадь по координатам вершин: сумма xᵢyᵢ₊₁ − xᵢ₊₁yᵢ, а её знак — направление обхода. O(n) 2 задачи GEO Приём Заметающая прямая Упростите берега мира до 0,2° — и в 72 местах они пересекутся. Прямая с запада на восток найдёт их все, сравнив только соседей. O((n + k) log n) 3 задачи GEO Алгоритм Триангуляция Делоне и диаграмма Вороного Зоны ближайшей точки и треугольники с пустыми окружностями: две стороны одной структуры. O(n log n) в среднем 2 задачи GEO Приём Вращающиеся калиперы У 971 из 2679 кварталов центра Алматы наименьший прямоугольник повёрнут на 4–8°: сетка улиц смотрит не строго на север. O(n) после оболочки, O(n log n) с ней 2 задачи

Задачи

Перекрёсток: внутри, снаружи или на границе Площадь забора Площадь района из нескольких кусков Где поставить новую часть Граница без петель Пронести в проём Сколько кругов Яблони в узлах сетки

Часто рядом

точки на плоскости 6 карты и навигация 6 геоданные 6 классика 5 олимпиады 3 пересечения 2 точность вычислений 2 игры 2 собеседования 2 оболочки 2 сортировка 1 стек 1