начинающимся в точке
начинающимся в точке C. При этом углы считаем “против часовой стрелки”, так что они могут иметь значения от 0 до 360 градусов. Теперь каждой вершине многоугольника соответствует число. Занумеруем вершины в порядке возрастания этих чисел: B1B2... BN. На это действие (сортировку) требуется время O(N logN).
*
Ответ на вопрос задачи.
Теперь для заданной точки A проведем луч CA и посчитаем для него угол с вертикальным лучом. Найдем, между какими двумя лучами CBi и CBi+1 проходит луч CA. Это можно сделать за время O(log N) - используя бинарный поиск, поскольку лучи расставлены в порядке возрастания (или убывания) угла. Теперь осталось только выяснить, лежит ли точка A внутри треугольника CBi_CBi+1.
Предложенный алгоритм работает не только для выпуклых многоугольников. Все, что нам реально требовалось - наличие точки внутри многоугольника, из которой “просматривается” весь многоугольник, т.е. такой, что любой выходящий из нее луч пересекает границу многоугольника ровно 1 раз. Наличие
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
