ли данная точка
ли данная точка A внутри данного многоугольника B1B2...Bn?
Это уже конкретнее. Добавим еще, что мы считаем многоугольник простым: это значит, что его стороны не имеют общих точек, кроме вершин, причем в каждой вершине встречаются ровно 2 стороны. С точки зрения здравого смысла, это вполне естественно, а с точки зрения программирования - упрощает задачу, но добавляет головной боли при проверке входных данных:
b)
Является ли данный многоугольник B1B2...Bn простым?
Эту задачу можно решить за время O(N2), просто перебрав все возможные пары отрезков и проверив, не пересекаются ли они. (Мы уже умеем это делать.) Вопрос о том, как решить эту задачу быстрее, мы сейчас обсуждать не будем.
Приведем теперь алгоритм решения примера для простого многоугольника за время O(n).
Если провести через точку A какую-нибудь прямую, она пересечет стороны многоугольника в четном числе точек. При этом на прямой будут чередоваться интервалы, находящиеся вне многоугольника и внутри него. Если
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
