Сортировка координат (x, y) параболы y = ax^2 + bx + c x = x1, x2, x3, x4. в соответствии с координатами у

Question

Я попробовал CPP кодоблок:

bool comp(const pair<int,int>&A, const pair<int,int>&B) 
{ 
    if(A.second<=B.second) 
    { 
     if(A.first>=B.first) 
      return 1; 
     else 
      return 0; 
    } 
    return 0; 
} 

int main() 
{ 
    int a, b, c, x[10], y[10]; 
    cin>>a; 
    cin>>b; 
    cin>>c; 
    for(int i=0;i<4;++i) 
    { 
     cin>>x[i]; 
     y[i]=a*x[i]*x[i]+b*x[i]+c; 
    } 
    vector<pair<int,int> >V; 
    for(int i=0;i<4;++i) 
    { 
     V.pb(mp(x[i],y[i])); 
    } 
    for(int i=0;i<4;++i) 
    { 
     sort(V.begin(),V.end(),&comp); 
    } 
    for(int i=0;i<V.size();i++) 
    { 
     cout<<V[i].first; 

     cout<<" "<<V[i].second<<" "; 
    } 

    return 0; 
} 

STDIN: a b c x1 x2 x3... и x в отсортированном порядке, т.е. x1 < x2 < x3. Код должен генерировать новый список (y = y1 y2 y3) с использованием уравнения параболы для каждого x и сортировать приведенный выше список со сложностью времени выполнения < = O (log n).
STDOUT: x3,y3 x1,y1 x2,y2 ... (предположительно вычислено y3 < y1 < y2..).
Код НЕ должен вычислять Y. Умножение на этом вычислительном узле «слишком» дорого. Решение должно идентифицировать способ сортировки списка без вычисления значений «y».
Мой код вычисляет значения y. Может ли кто-нибудь найти метод сортировки без вычисления значений y. Реализация кода на Python также будет работать для меня.

Answer 1

Чем дальше x значение от вершины параболы по x0, тем выше его значение, когда ya положительна, а нижний его значение y, когда a отрицательный.

|x1 - x0| > |x2 - x0| && a > 0 --> y1 > y2 
    |x1 - x0| > |x2 - x0| && a < 0 --> y1 < y2 

Когда a равен нулю, ваша парабола действительно линия и x значения уже отсортированы в правильном порядке, когда b положительна или в обратном порядке, когда b отрицательный.

Так что, когда a не равен нулю, найти апекс:

x0 = - b/(2*a) 

Теперь найти значение в вашей отсортированном списке x значений, которое ближе всего к x:

i = index(x: min(|x - x0|)) 

Добавить точку i к списку. Создание двух индексов:

l = i - 1 
    r = i + 1 

Теперь возьмите точку в любом индексе l или r, который находится ближе к вершине, и добавить его в список. Обновите индекс до исчерпания списка.

Отклонить список, если a отрицательный. (Или добавьте элементы из конца списка.)

Редактировать: Вот реализация в Python. Он вытесняет элементы из подписок, а не использует индексы массивов, но логика такая же:

import bisect 

def parasort(a, b, c, x): 
    """Return list sorted by y = a*x*x + b*x + c for sorted input x.""" 

    if not x: 
     return x 

    if a == 0:       # degenerate case: line 
     if b < 0: return x[::-1] 
     return x[:] 

    x0 = -0.5 * b/a     # apex of parabola 

    i = bisect.bisect_left(x, x0) + 1 # closest point via bin. search 
    l = x[:i][::-1]      # left array, reverted 
    r = x[i:]       # right array 

    res = [] 

    while l and r:      # merge l and r 
     if x0 - l[0] > r[0] - x0:  # right item is smaller 
      res += [r.pop(0)] 
     else:       # left item is smaller 
      res += [l.pop(0)] 

    res += l + r      # append rest of arrays 

    if a < 0: return res[::-1]   
    return res 



a = 4 
b = 0 
c = 0 
xx = parasort(a, b, c, [-3, 0, 1, 2]) 

for x in xx: 
    print x, a*x*x + b*x + c