Bir parabolün koordinatlarını (x, y) sıralayın. Y = ax^2 + bx + c x = x1, x2, x3, x4. y e göre bir kod-bloğu cpp çalıştılar

Question

koordinatları:

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... ve x yani x1 < x2 < x3 sıralanmış düzenindedir. Kod her x için parabol denklemini kullanarak yeni bir liste (y = y1 y2 y3) oluşturmalı ve yukarıdaki listeyi < = O (log n) çalışma zamanı karmaşıklığı ile sıralamalıdır.
STDOUT: x3,y3 x1,y1 x2,y2 ... (hesaplanan y3 < y1 < y2.. varsayar).
Kod, Y'leri YORUMLANMAMALIDIR. Bu hesaplama düğümünde çoğaltma "çok" maliyetlidir. Çözüm, "y" değerlerini hesaplamadan listeyi hala sıralama yolu belirlemelidir.
Kodum, y değerlerini hesaplar. Y değerlerini hesaplamaksızın herhangi bir sıralama yöntemi bulabilir. Bir python kodu uygulaması da benim için çalışacaktı.

Answer 1

uzak bir x değeri a negatif olduğunda a düşük seviyede y değeri pozitif olduğunda ve daha yüksek olan y değerdir, parabol en tepe noktasına x0 arasındadır. a sıfır olduğunda

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

, senin parabol gerçekten bir çizgidir ve b negatif olduğunda b pozitif veya ters sırada iken x değerleri zaten doğru sırayla sıralanır.

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

noktası i ekleyin:

x0 = - b/(2*a) 

Şimdi x en yakın olan x değerlerin sizin sıralı listede değeri bulmak: a değil sıfır olduğunda

Yani, açıyı bulmaya listeye İki endeks oluşturun:

l = i - 1 
    r = i + 1 

Şimdi endeksi l veya apekse yakın r ya noktayı alıp listeye eklemek. Listeyi bitirene kadar dizini güncelleyin.

a negatif olduğunda listeyi geri alın. (Veya listenin sonundaki öğeleri ekleyin.)

Edit: İşte Python'da bir uygulama. Dizi indekslerini kullanmak yerine alt listelerden eleman çıkarır ancak mantık aynıdır:

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