Изменения

Будем хранить 2 массива : <math>front[]</math> - начало <math>x</math>-координаты, начиная с которых прямые совпадают с выпуклой оболочкой (по т.е. i-я прямая совпадает с выпуклой оболочкой текущего множества прямых при <math>x<tex>\in</tex> [front[i]; front[i + 1])</math>) соответствующей прямой выпуклой оболочки и <math>st[]</math> - номер этой прямой (в глобальной нумерации). Также воспользуемся тем, что <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>x = z+1</math>