Проверка на то что точка лежит внутри многоугольника

Материал из Algocode wiki
Версия от 14:18, 19 декабря 2020; Глеб (обсуждение | вклад) (Новая страница: «==Идея== Если зафиксировать какую-либо вершину, то относительно нее углы будут расположе...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Идея

Если зафиксировать какую-либо вершину, то относительно нее углы будут расположены против часовой стрелки или против часовой стрелки, при этом несложно заметить, что сначала угол к вершине будет меньше/больше угла к нашей точке, а затем наоборот, следовательно, мы можем сделать бинпоиск и найти первую вершину угол от которой больше/меньше нашего.

</syntaxhighlight>


Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin