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

Что решает

пересечения

Статьи

GEO Приём Векторы и ориентация Знак векторного произведения — поворот налево или направо; на нём стоит почти вся вычислительная геометрия. O(1) на один поворот 2 задачи GEO Алгоритм Пересечение отрезков Где встречаются два отрезка — точно, в дробях; и как найти все встречи среди тысяч отрезков без перебора пар. O(1) на пару; O(n²) перебором для n отрезков 2 задачи GEO Приём Заметающая прямая Упростите берега мира до 0,2° — и в 72 местах они пересекутся. Прямая с запада на восток найдёт их все, сравнив только соседей. O((n + k) log n) 3 задачи

Задачи

Где встречаются отрезки Пересекаются ли отрезки В одном предложении Граница без петель Мосты и тоннели

Часто рядом

карты и навигация 3 геоданные 3 точки на плоскости 2 многоугольник 2 точность вычислений 2 игры 2 классика 2 собеседования 2 олимпиады 1 хеширование 1 заметающая прямая 1 дерево отрезков 1