Изменения

Заметим, что условия на прямые, что <math>k[i]</math> возрастает/убывает и <math>x[i]</math> убывает/возрастает выглядят не достаточно общими. Как же быть, если в задаче таких ограничений нет. Иногда можно отсортировать прямые нужным образом, не испортив свойств задачи (пример : задача G отсюда http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdf).

Но рассмотрим общий случай. Наша задача поменялась следующим образом : по-прежнему у нас есть выпуклая оболочка, имея которую мы за <math>O(logn)</math> или быстрее можем найти <math>dp[i]</math>, но теперь вставку i-й прямой в оболочку уже нельзя выполнить старым способом за <math>O(1)</math> (в среднем). У нас есть выпуклая оболочка, наша прямая пересекает ее, возможно, «отрезая» несколько отрезков выпуклой оболочки в середине (рис. 4).

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