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

Конспект написан не до конца, но основные вещи уже есть.

Выпуклый многоугольник

Начнём с того, что выпуклый многоугольник нам задан как замкнутая полилиния. Поэтому для любой вершины этого многоугольника все остальные точки будут отсортированы по углу. Возьмём первую точку многоугольника и мысленно проведём от неё все лучи, содержащие диагонали. За линию можно пройтись по всем получившимся углам и понять, в каком из них лежит точка. Когда мы нашли угол, за константное время проверяем, с какой стороны от ребра многоугольника лежит точка. Итоговое время работы: [math]O(n)[/math].