I have $$$n$$$ lines in the form: $$$y_i=a_i x+b_i$$$, where $$$1\leq n \leq 10^6$$$ and $$$-10^9 \leq a, b \leq 10^9$$$. I need to know how many different lines has the maximum value at some $$$x$$$ (possible $$$x=0$$$).
For example:
At $$$x=0$$$, the lines $$$y_1$$$ and $$$y_2$$$ has the maximum value ($$$20$$$) for that $$$x$$$, but in $$$x=1$$$ just the line $$$y_3$$$ has the maximum value ($$$39$$$), so the answer is 3, because all of them has the maximum value for some $$$x$$$. How can I implement that?
Thanks in advance
There is such thing as Convex Hull Trick (read about here https://codeforces.net/blog/entry/63823 for example). So you need just build it. 1. Sort lines by a 2. If two lines have same a, remove one with least b. 3. And do same things with stack as in tutorial.