Как найти самый большой y-пересечение линий через заданные точки (a, b) и (x, 0)?

Question

Я дал очки (a, b) и тогда я дал очки (x, 0), Теперь для каждой точки (x, 0) Я делаю линии со всеми точками (a, b) (см. изображение).
Для каждой точки (x, 0) Я должен вернуть индексы точки / точек (a, b)какой у-пересечение линии через эту точку / точки и точки (x, 0) самый большой.
Все значения х точек (x, 0) больше максимума a, чисел a, b, x являются положительными целыми числами.

Пример:

вход

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)) 

Выход

1
0 2
0
1

Мое решение:

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;
}

Мое решение этой проблемы имеет временную сложность O(m * n), но это не кажется мне очень эффективным. Мой вопрос: можно ли решить эту проблему с лучшей временной сложностью и как?

Answer 1

Постройте выпуклый корпус для точек a/b, получите только верхнюю половину (на самом деле вам нужна только правая нога верхнего конверта) в порядке от самой правой точки

Сортировать х-баллы

Сложность о O(mlogm + nlogn) (в зависимости от корпуса и методов сортировки)

Пройдите x-list в порядке от маленьких значений, находя лучшие пункты набора a/b. Обратите внимание, что этот процесс является линейным O(n+m) (мы найдем следующую лучшую точку a/b только слева от текущей точки - представьте вращающуюся палку, один конец которой движется вдоль оси OX, другой конец опирается на набор точек a/b)

Answer 2

Большинство шагов здесь кажутся довольно очевидными:

1. читать в пунктах
2. читать в X-перехват для каждой строки (я только что изобрел "X-перехват"?)
3. вычислить наклоны линий
4. выберите самый маленький уклон
5. найти все линии с этим наклоном
6. распечатать результаты

Я считаю, что все это может быть сделано со сложностью O(N), поэтому в целом должно быть O(N).

#include <vector>
#include <algorithm>
#include <iostream>
#include <iterator>

struct point {
    int x;
    int y;

    friend std::istream &operator>>(std::istream &is, point &p) {
        return is >> p.x >> p.y;
    }

    friend std::ostream &operator<<(std::ostream &os, point const &p) {
        return os << "(" << p.x << ", " << p.y << ")";
    }
};

struct slope_index {
    double slope;
    int index;

    bool operator<(slope_index const &other) const {
        return slope < other.slope;
    }

    bool operator==(slope_index const &other) const {
        return slope == other.slope;
    }
};

int main() {
    int N;
    std::cin >> N;

    // read in the points
    std::vector<point> points;
    std::copy_n(std::istream_iterator<point>(std::cin), N, std::back_inserter(points));

    // read in the X-intercept for each point:
    std::vector<int> Xs;
    std::copy_n(std::istream_iterator<int>(std::cin), N, std::back_inserter(Xs));

    // compute the slopes
    std::vector<slope_index> slopes;
    int i = 0;
    std::transform(points.begin(), points.end(),
        Xs.begin(),
        std::back_inserter(slopes),
        [&](point const &p, int currX) { return slope_index{ p.y / double(p.x - currX), i++ }; });

    // find the smallest slope
    auto v = *std::min_element(slopes.begin(), slopes.end());

    // find all the lines with that slope:
    auto pos = std::partition(slopes.begin(), slopes.end(), [&](auto const &s) { return v == s; });

    // print out the results:
    for (auto s = slopes.begin(); s != pos; ++s)
        std::cout << points[s->index];
}