code_hard123's blog

How to solve this problem ?
By code_hard123, history, 8 years ago, In English

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!

  • Vote: I like it
  • +23
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Why are both the functions monotonically decreasing?

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

    spoiler
    → Reply