The deque approach assumes slopes are sorted (decreasing for lower envelope). What if they're not? Option 1: Binary search on the hull. Insert each line, but use binary search to find its position. per operation. Option 2: Li Chao tree. A segment tree over x-coordinates.
Each node stores the optimal line for its range. insert and query. Option 3: Process offline. Sort all operations, then use deque. Works when you can reorder.