виде (к ним добавляются
виде (к ним добавляются некоторые дополнительные сведения). Эта часть программы работает за время O(N logN).
*
Собственно ответ на вопрос задачи. Используя полученные в процессе предварительной обработки сведения, мы за время O(logN) определяем для заданной точки, лежит ли она внутри многоугольника.
Разделение на такие две части типично для геометрических (и не только геометрических) задач. При этом предварительная обработка вполне может выполняться дольше, чем однократное решение. Тем не менее, описанный подход может быть полезен в одном из 2-х случаев: если задачу нужно решать многократно, либо если обработку данных можно произвести заранее, а ответы на вопросы придется получать в реальном времени.
Наш алгоритм будет работать для случая выпуклого многоугольника.
*
Предварительная обработка.
Возьмем точку C внутри многоугольника. Для всех лучей с началом в точке C, проходящих через вершины многоугольника, посчитаем углы, которые они образуют с вертикальным лучом,
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
