186
правок
Изменения
→Р.Реализация
'''while''' (1) {
j = st[sz - 1]
x = divide(B[j] - B[i], K[i] - K[j]) <font color=green>// x-координата пересечения с последней прямой оболочки, округленное в нужную сторону (*) </font >
if (x > from[sz - 1]) '''break''' <font color=green>// перестаем удалять последнюю прямую из множества, если новая прямая пересекает ее позже, чем начинается ее "область действия" </font >
--sz <font color=green>// удаляем последнюю прямую, если она лишняя </font >
}
}
(Здесь функция divide(a, b) возвращает нужное (*) округление a / b)
Такая реализация будет работать за O(n).
