Изменения

Перейти к: навигация, поиск
м
rollbackEdits.php mass rollback
{{ready}}
== Выпуклый многоугольник ==
Выпуклый многоугольник задан как замкнутая полулинияполилиния, поэтому для любой вершины этого многоугольника все остальные точки будут отсортированы по углу. Возьмём первую точку многоугольника и мысленно проведём от неё все лучи, содержащие диагонали. Бинпоиском за логарифм можно пройтись по углам и понять, в каком из них лежит точка. Когда найден угол, за константное время можно проверить, с какой стороны от противолежащего первой точке ребра многоугольника лежит точка.
Итоговый алгоритм:
1632
правки

Навигация