355
правок
Изменения
Новая страница: «{{ptready}} == Выпуклый многоугольник == Начнём с того, что выпуклый многоугольник нам задан ка...»
{{ptready}}
== Выпуклый многоугольник ==
Начнём с того, что выпуклый многоугольник нам задан как замкнутая полилиния. Поэтому для любой вершины этого многоугольника все остальные точки будут отсортированы по углу. Возьмём первую точку многоугольника и мысленно проведём от неё все лучи, содержащие диагонали. За линию можно пройтись по всем получившимся углам и понять, в каком из них лежит точка (для альтернативно одарённых: повороты должны различаться). Когда мы нашли угол, за константное время проверяем, с какой стороны от ребра многоугольника лежит точка (для альтернативно одарённых: это проверяется поворотом). Итоговое время работы: <tex>O(n)</tex>.
(Для альтернативно одарённых: точка может не лежать ни в каком угле, то есть быть правее самого правого ребра или левее самого левого, в этом случае она не лежит внутри многоугольника)
== Невыпуклый многоугольник ==
== Выпуклый многоугольник ==
Начнём с того, что выпуклый многоугольник нам задан как замкнутая полилиния. Поэтому для любой вершины этого многоугольника все остальные точки будут отсортированы по углу. Возьмём первую точку многоугольника и мысленно проведём от неё все лучи, содержащие диагонали. За линию можно пройтись по всем получившимся углам и понять, в каком из них лежит точка (для альтернативно одарённых: повороты должны различаться). Когда мы нашли угол, за константное время проверяем, с какой стороны от ребра многоугольника лежит точка (для альтернативно одарённых: это проверяется поворотом). Итоговое время работы: <tex>O(n)</tex>.
(Для альтернативно одарённых: точка может не лежать ни в каком угле, то есть быть правее самого правого ребра или левее самого левого, в этом случае она не лежит внутри многоугольника)
== Невыпуклый многоугольник ==
