Hi. I recently overcomplicated one easy-ish geometry problem and encountered the following difficulty.
Let's say I have a set of linear functions f(x) = ax + b and two types of online queries:
- Given a and b, insert a new linear function.
- Given x0, print the maximum value f(x0).
I can handle both queries in logarithmic time by using BST and maintaining the convex hull of linear functions. Can I do the same (easily?) using
set in C++? The problem is that the second query requires
lower_bound that is able to say whether a linear function is on the left or on the right from the optimal one. I think it's impossible because it depends on the neighboring (after sorting CH by slope) functions.
During a contest, I implemented something in O(log2) — a lower_bound that runs an internal lower_bound to find the next linear function in the set. Later I came up with an idea to extend a linear-function struct to also store a copy of the next function in the set. It requires some extra work but should work and should be O(log), right? Do you see any easier way?