Изменения
→Детали реализации:
Теперь пусть новая прямая пересекает последнюю прямую множества раньше, чем предпоследнюю (рис.1), последняя прямая при любых x лежит выше какой-то другой прямой множества и значит ее можно удалить, чтд.
==Детали реализации:==
Будем хранить 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.
==Р.Реализация==
st[0] = 0
