Изменения

Будем хранить 2 массива (имитирующих стеки) : <math>front[]</math> и <math>st[]</math> - начало (по x) соответствующей прямой выпуклой оболочки и номер этой прямой (в глобальной нумерации). Также воспользуемся тем, что <math>x[i] = a[i]</math> возрастают (по условию задачи), а значит мы можем искать первое такое <math>j</math>, что <math>x[i] >= front[j]</math> не бинарным поиском, а методом 2х указателей за <math>O(n)</math> суммарно. Также массив front[] можно хранить в целых числах, округляя х-координаты в сторону лежащих правее по оси x до ближайшего целого (*). Почему так? На самом деле мы, считая динамику, подставляем в уравнения прямых только целые <math>x[i]</math>, а значит если <math>k</math>-я прямая пересекается с <math>k+1</math>-й в точке <math>z + </math> <tex>\alpha</tex> (z-целое, <tex>\alpha</tex> <tex>\in</tex> <math>[0;1)</math>), то мы будем подставлять <math>z</math> или <math>z + 1</math>. Поэтому можно считать, что новая прямая имеет "область действия", начиная с <math>z+1</math>