Hello all,

I have tried googling this a lot but can't find a good solution. So any help will be greatly appreciated.

today, when I was doing the NOI, I came across a question which required me to use the convex hull trick. This is usually quite standard and easy to implement except for one thing: gradients of the lines can be a fraction. Let me explain:

The "line" that I am talking about isn't really a line. An example would be y = [mx] + c, where [x] means the largest integer small than or equal to x. (yes i know that it's not the right symbol but idk how to write mathematical symbols. Sorry for the inconvenience). If you plug this into desmos, it looks like a staircase. But i'm pretty sure that I can just use the line y = mx + c because if a certain line y = mx + c is minimum at a certain x then it will also be minimum when you take the floor. I have just explained this as maybe there is a different method for this kind of line, so if there is please let me know. Note that here, m can be fractional.

So now the problem is the standard convex hull trick with fractional gradients. However, I don't think using a fraction is correct as when you use fractions, the denominator can get quite large (potentially even bigger than 64 bit int). Also, using floats can, obviously, lead to precision errors.

So please help with a way to implement such a convex hull.

Also some additional information — there aren't really any update queries. You just add all of the lines to the hull at the start, then do all the queries. After queries, you don't have to add anymore lines. Also, all line gradients are negative, and queries can be either decreasing or increasing. (i can implement the solution such that the queries are either increasing or decreasing). So it is basically ur choice if you want queries to be increasing or decreasing, though I don' think it will make much of a difference.

Thank you so much for reading! And any help would be great!