Как найти самый большой y-пересечение линий через заданные точки (a, b) и (x, 0)?
Я дал очки (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), но это не кажется мне эффективным. Мой вопрос: можно ли решить эту проблему с лучшей временной сложностью и как?
Решение
строить выпуклый корпус за очки а / б получи только верхнюю половину (на самом деле вам нужна только правая нога верхнего конверта) в порядке от самой правильной точки
Сортировать х-баллы
Сложность о O(mlogm + nlogn) (в зависимости от корпуса и методов сортировки)
Пройдите x-list в порядке от маленьких значений, находя лучшие пункты набора a / b. Обратите внимание, что этот процесс является линейным O(n+m) (мы найдем следующую лучшую точку a / b только слева от текущей точки — представьте вращающуюся палку, один конец которой движется вдоль оси OX, другой конец опирается на набор точек a / b)
Другие решения
Большинство шагов здесь кажутся довольно очевидными:
- читать в пунктах
- читать в X-перехват для каждой строки (я только что изобрел «X-перехват»?)
- вычислить наклоны линий
- выберите самый маленький уклон
- найти все линии с этим наклоном
- распечатать результаты
Я считаю, что все это может быть сделано со сложностью 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];
}