Определить две самые близкие к началу координат точки из n имеющихся
подскажите пожалуйста как можно перебрать весь вектор pair и выбрать оттуда и две самые близкие в началу координат? Перебирать такой формулой (прикрепляю) все координаты через циклы и сравнивать = самоубийство Может кто знает как можно это быстрее сделать? Спасибо заранее
a = sqrt((V[i].first * V[i].first) + (V[i].second * V[i].second));
b = sqrt((V[j].first * V[j].first) + (V[j].second * V[j].second));
Ответы (1 шт):
В вашей постановке - если готовая функция - то просто применить nth_element, примерно как
auto it = nth_element(v.begin(),v.begin()+2,v.end(),
[](auto a, auto b)
{ return a.first*a.first +a.second*a.second <
b.first*b.first +b.second*b.second; });
Замечу, что sqrt тут не нужен.
О сложности nth_element:
O(N) applications of the predicate, and O(N log N) swaps, where N = last - first.
Но руками, поддерживая два минимальных значения и сравнивая каждый элемент с ними - это вычисление (расстояния) получится n раз.
Если массив огромный или надо делать такое часто - лучше при каждом элементе держать его расстояние до начала координат для повышения эффективности...