对抛物线的坐标 (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。此计算节点上的乘法运算成本 "too"。该解决方案应确定一种无需计算 "y" 值即可对列表进行排序的方法。
我的代码计算 y 值。谁能找到一种不计算 y 值的排序方法。 python 代码实现也适用于我。

Answer 1

x值离抛物线的顶点x0越远，当a为正时，y值越高，[=17=越低=] 当 a 为负数时的值。

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

当 a 为零时，您的抛物线实际上是一条线，并且当 b 为正时 x 值已按正确顺序排序，或者当 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

对抛物线的坐标 (x,y) 进行排序 y=ax^2+bx+c x=x1,x2,x3,x4。根据y坐标

Sort coordinates (x,y) of a parabola y=ax^2+bx+c x=x1,x2,x3, x4. according to y coordinates

c++

arrays

sorting

algorithm

computational-geometry