How to find largest y-intercept of lines through given points (a, b) and (x, 0)?

Question

I have given points (a, b) and then I have given points (x, 0). Now for each point (x, 0) I make lines with all points (a, b) (see image).
For each point (x, 0) I have to return indexes of thease point/points (a, b) which y-intercept of line through this point/points and point (x, 0) is largest.
All x values of points (x, 0) are greater than maximum a. Numbers a, b, x are positive integers.

Example:

Input

3 4 (number of (a, b) points and number of (x, 0) points - let's call them m and n)
5 3 (point A, index 0)
14 1 (point C, index 1)
10 2 (point B, index 2)
16 20 40 15 (x values of points (x, 0)) 

Output

1
0 2
0
1

My solution:

int main() {
    int m, n;
    cin >> m >> n;
    vector<pair<int, int>> pointsAB(m);

    for (int i = 0; i < m; ++i) {
        cin >> pointsAB[i].first >> pointsAB[i].second;
    }

    for (int j = 0; j < n; ++j) {
        int currX;
        double minSlope = 1.00;
        vector<int> indexes;
        cin >> currX;
        for (int i = 0; i < m; ++i) {
            int a = pointsAB[i].first, b = pointsAB[i].second;
            double currSlope = -((double)b) / (currX - a);
            if (currSlope < minSlope) {
                indexes.clear();
                minSlope = currSlope;
                indexes.push_back(i);
            }
            else if (currSlope == minSlope) {
                indexes.push_back(i);
            }
        }

        cout << indexes[0];
        for (int k = 1; k < indexes.size(); ++k) {
            cout << " " << indexes[k];
        }
        cout << '\n';
    }

    return 0;
}

My solution to this problem has time complexity O(m * n) but this doesn't seem very efficient to me. My question is can be this problem solved with better time complexity and how?

Answer 1

Build convex hull for a/b points, get only top half (really you need only right leg of upper envelope) in order from the most right point

Sort x-points

Complexity is about O(mlogm + nlogn) (depending on hull and sorting methods)

Walk through x-list in order from small values, finding the best points of a/b set. Note that this process is linear O(n+m) (we will find next best a/b point only to the left of current one - imagine rotating stick, one end moves along OX axis, another end rests on the a/b point set)