I recently read the article from PEG Wiki about the convex hull trick, which can be applied to speed up dynamic programming algorithms (Link to the website) . This optimisation can only apply when certain conditions are met. Surprisingly, at the end of the article I read that we can achieve a fully dynamic variant of the trick (meaning that there are no conditions of applicability) if we store the lines in a
std::set. Although I have understood the approach mentioned, I always fail when I try to implement it. Could someone point me to an implementation of the dynamic convex hull trick, and some problems where I can practice it? Thanks in advance.