# ли данная точка

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

Индекс
Элементарные функции Линейные уравнения Нелинейные уравнения Случайные числа