Начнём с того, что выпуклый Выпуклый многоугольник нам задан как замкнутая полилиния. Поэтому , поэтому для любой вершины этого многоугольника все остальные точки будут отсортированы по углу. Возьмём первую точку многоугольника и мысленно проведём от неё все лучи, содержащие диагонали. За Бинпоиском за логарифм можно пройтись бинпоиском по углам и {{Acronym|понять, в каком из них лежит точка|Для альтернативно одарённых: повороты должны различаться. А ещё кому-то может показаться неочевидным тот факт, что точка может лежать левее самой левой грани или правее самой правой. Это тоже надо сразу проверить}}. Когда мы нашли найден угол, за константное время {{Acronym|проверяемможно проверить, с какой стороны от противолежащего первой точке ребра многоугольника лежит точка|для альтернативно одарённых. Итоговый алгоритм: это проверяется поворотом * если искомая точка <tex>q</tex> лежит левее самой левой грани или правее самой правой, сразу возвращаем false* бинпоиском ищем такое ребро <tex>a_i a_{i+1}</tex>, не инцидентное самой первой точке <tex>a_0</tex> заданного многоугольника, что повороты точек <tex>a_0, a_i, q</tex> и <tex>a_0, a_{i+1}, q</tex> различаются* проверяем поворот точек <tex>a_i, a_{i+1}. , q</tex>, если он левый — точка лежит внутри, если правый — снаружи Итоговое время работы: <tex>O(\log n)</tex>.
