Изменения

Будем хранить 2 массива (имитирующих стеки) : front[] и st[] - начало (по x) соответствующей прямой выпуклой оболочки и номер этой прямой (в глобальной нумерации). Также воспользуемся тем, что x[i] = a[i] возрастают (по условию задачи), а значит мы можем искать первое такое j, что x[i] >= front[j] не бинарным поиском, а методом 2х указателей за O(n) суммарно. Также массив front[] можно хранить в целых числах, округляя х-координаты в сторону лежащих правее по оси x.

==Р.Реализация==

from[0] = -∞

sz = 1 // текущий размер выпуклой оболочки

st[sz] = i

from[sz++] = x

(Здесь функция divide(a, b) возвращает нужное округление a / b)

Такая реализация будет работать за O(n).