Изменения

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

Навигация