Изменения
→Реализация
sz = 1 <font color=green>// текущий размер выпуклой оболочки </font>
pos = 1 <font color=green>// текущая позиция первого такого j, что x[i] >= front[st[j]] </font >
'''for''' i = 2..n {
'''while''' (front[pos] < x[i]) <font color=green>// метод 1 указателя (ищем первое pos, такое что x[i] покрывается "областью действия" st[pos]-той прямой </font >
pos = pos + 1
j = st[pos]
dp[i] = K[j] * <math>\cdot</math>a[i] + B[j] '''if''' (i < n) { <font color=green>// если у нас добавляется НЕ последняя прямая, то придется пересчитать выпуклую оболочку </font >
K[i] = c[i] <font color=green>// наши переобозначения переменных </font >
B[i] = dp[i] <font color=green>// наши переобозначения переменных </font >
x = -<tex>\infty</tex>
'''while''' (''true'') {
j = st[sz]
x = divide(B[j] - B[i], K[i] - K[j]) <font color=green>// x-координата пересечения с последней прямой оболочки, округленное в нужную сторону (*) </font >
'''if''' (x > from[sz]) '''break''' <font color=green>// перестаем удалять последнюю прямую из множества, если новая прямая пересекает ее позже, чем начинается ее "область действия" </font >
sz = sz - 1<font color=green>// удаляем последнюю прямую, если она лишняя </font >
st[sz + 1] = i
from[sz + 1] = x <font color=green>// добавили новую прямую </font >
sz = sz + 1
'''return''' dp[n]
Здесь функция divide(a, b) возвращает нужное(*) округление a / b. Приведем её код :
