186
правок
Изменения
→Динамический convex hull trick
Т.е. нужно уметь быстро (за <math>O(logn)</math>?) назодить, после какой прямой стоит пытаться вставить текущую (красную рис.4) прямую и удалять лишние справа, начиная с нее, потом проводить аналогичные операции слева. Итак, давайте хранить <math>std::set</math> (или любой аналог в других языках) пар <math><k, st></math> = <коэффицент прямой, ее номер в глобальной нумерации>. Когда приходит новая прямая, делаем lower_bound - 1 в сете, т.е. ищем ближайшую прямую с меньшим углом наклона, и начиная с нее повторяем старый алгоритм (удаляем, пока прямая бесполезная). И симметричный алгоритм применяем ко всем прямым справа от нашей.
Асимптотика решения составит <math>O(logn)</math> на каждый из n запросов «добавить прямую» + <math>O(n)</math> суммарно на удаление прямых. Итго Итого <math>O(nlogn)</math>.
== Альтернативный подход ==
