Изменения

Заметим, что условия на прямые, что <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).