Given N points in two dimensional space and Q queries. In each query, given two non negative integers a , b. Find the point (x,y) such that F(x,y) is minimum, where F(x,y) = a * x + b * y

Constraints:

1 <= N <= 10^6

1 <= Q <= 10^5

0 <= a , b <= 10^9

0 <= |x| , |y| <= 10^9

Thank You!

Choose for every given

xminimalyamong all points with thisx. Sincea> 0,b> 0 it`s reasonable to choose for bigger values ofxsmaller values ofy. I mean the sequence of choseny-values must be monotonically decreasing: . Consider two functions:f(x) =axandg(x) =by_{x}, wherey_{x}denotes the y-value corresponding to the givenx. One monotonically increasing while another monotonically decreasing. Seems like minimum of their sum may be found through ternary search byx.Why are both the functions monotonically decreasing?

How is g(x) supposed to be monotonically decreasing? Seems like the y-value is independent of the x value.

Let v < u if v.x < u.x and v.y < u.y, consider the smallest points, red points in image, and apply a ternary search to minimize the function since necessarily with a, b ≥ 0 if u < v then A.u <= A.v (A = (a, b) and . is dot product), I hope you understand, I'm not good at explaining xD.

Consider any red point and any a and b ≥ 0, prove that the function is convex (respect to red points).

spoilerlet v such that a*v.x + b*v.y is the least possible, as ax + by has not positive tangent, (consider red points) if u.x ≥ v.x then a*u.x + b*u.y ≥ a*v.x + b*v.y else a*u.x + b*u.y ≤ a*v.x + b*v.y