Изменения

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