### code_hard123's blog

By code_hard123, history, 7 years ago,

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!

• +23

 » 7 years ago, # | ← Rev. 4 →   0 Choose for every given x minimal y among all points with this x. Since a > 0, b > 0 it`s reasonable to choose for bigger values of x smaller values of y. I mean the sequence of chosen y-values must be monotonically decreasing: . Consider two functions: f(x) = ax and g(x) = byx, where yx denotes the y-value corresponding to the given x. One monotonically increasing while another monotonically decreasing. Seems like minimum of their sum may be found through ternary search by x.
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 Why are both the functions monotonically decreasing?
•  » » 7 years ago, # ^ |   0 How is g(x) supposed to be monotonically decreasing? Seems like the y-value is independent of the x value.
 » 7 years ago, # | ← Rev. 3 →   0 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.
•  » » 7 years ago, # ^ | ← Rev. 3 →   0 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