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

Идея

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

</syntaxhighlight>

---

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

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