Изменения

Будем хранить 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до ближайшего целого.