Изменения

'''void''' Convex-hull-trick st[0] = 0 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 > ++pos j = st[pos] dp[i] = K[j] * a[i] + B[j] '''if''' (i < n - 1) { <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 - 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 > } }