How to solve SPOJ GOODG?

I was solving questions related to convex hull trick then I got stuck at this one but the lines will not be sorted, of course. So, I tried to to implement a Li Chao tree but it does not does not work. Any help will be appreciated.