Изменения

from[0] = -<tex>\infty</tex><font color=green>// первая прямая покрвает все x-ы, начиная с -∞</font> sz = 1 <font color=green>// текущий размер выпуклой оболочки</font> pos = 0 <font color=green>// текущая позиция первго такого j, что x[i] >= front[st[j]]</font > '''for ''' i = 1..n-1 { '''while ''' (front[pos] < x[i]) <font color=green>// метод 1 указателя (ищем первое pos, такое что x[i] покрывается "областью действия" st[pos]-той прямой </font >

dp[i] = K[j] * a[i] + B[j] '''if ''' (i < n - 1) { <font color=green>// если у нас добавляется НЕ последняя прямая, то придется пересчитать выпуклую оболочку </font > K[i] = bc[i] <font color=green>// наши переобозначения переменных </font > B[i] = dp[i]<font color=green>// наши переобозначения переменных </font > x = -inf<tex>\infty</tex> '''while ''' (1) {

x = divide(B[j] - B[i], K[i] - K[j])<font color=green>// x-координата пересечения с последней прямой оболочки, округленное в нужную сторону </font > if (x > from[sz - 1]) '''break''' <font color=green>// перестаем удалять последнюю прямую из множества, если новая прямая пересекает ее позже, чем начинается ее "область действия" </font > --sz<font color=green>// удаляем последнюю прямую, если она лишняя </font >

st[sz] = i from[sz++] = x<font color=green>// добавили новую прямую </font > }