Dynamic Programming Optimization-Convex hull Trick



I am trying to learn and understand convex hull trick.

I searched various discussions, and all point to wcipeg, which is down.

I know about cp-algorithms, can someone please provide any resources which explain it for beginners?
And also a few problems to start on with.


Sadly cp algorithms have a bad explanation for Convex hull Trick.
I learnt from https://codeforces.com/blog/entry/8219


I think this video would be helpful.
For the problems, you can follow @aryanc403’s link.


The WCIPEG page is well preserved here: http://web.archive.org/web/20181030143808/http://wcipeg.com/wiki/Convex_hull_trick


I think convex-hull trick is a neat (although very specific) technique, and I have considered writing a tutorial for it. Would that be a good idea?


It would be helpful for everyone.


I too recommend that video. I also watched that :slight_smile:


And I’m told that the PEG wiki is down only temporarily. It’s being fixed.


Okay, great!