拋物線的排序座標（x，y）y = ax^2 + bx + c x = x1，x2，x3，x4。根據y座標

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。該代碼應該使用每個x的拋物線方程生成一個新列表（y = y1 y2 y3），並將運行時複雜度爲< = O（log n）的上述列表排序。
STDOUT：x3,y3 x1,y1 x2,y2 ...（假設計算爲y3 < y1 < y2..）。
代碼不應該計算Y's。在這個計算節點上的乘法「太」成本高。該解決方案應該確定一種仍然排序列表而不計算「y」值的方法。
我的代碼計算y值。任何人都可以找到一種排序方法，無需計算y值。一個python代碼實現也適用於我。

Answer 1

越遠的x值是從拋物線的頂點x0，較高的是其y值時a爲正和下部其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