给出一个枢轴点，按照与枢轴点成的角度递增的顺序对一组点进行排序

Question

如标题中所述，我们需要按角度的升序对点进行排序。

我正在使用带有枢轴点和其他点的叉积。 如果考虑具有枢轴点的任意两个点的叉积为正，则表示这两个点按升序排序。

我无法在这个想法中找到错误，但这是行不通的。代码是：

//Here,a[0] is the pivot point.

//pivot is a global variable assigned to a[0].

vector<pair<int, int>>a(n);

sort(a.begin() + 1, a.end(), comp);

int comp(pair<int, int> x, pair<int, int> y) {
    int cross_product = crpd(pivot, x, y);

    if (cross_product >= 0)
        return 1;

    return 0;
}

int crpd(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
    //y2*x1 - y1*x2
    int y2 = a.second - c.second;
    int x2 = a.first - c.first;
    int y1 = a.second - b.second;
    int x1 = a.first - b.first;
    int ans = x1 * y2 - x2 * y1;
    return ans;
}

Sample Input:

Pivot: (0,-4)

Points: [ (-5,0) , (-5,1) , (-4,2) , (-3,3) , (-1,4) , (5,0) , (4,-3) , (0,-4) , (-4,-3) ] 
Expected Output: [ (4,-3) , (5,0) , (-1,4) , (-3,3) , (-4,2) , (-5,1) , (-5,0) , (-4,-3) ]
Displayed Output: [ (-5,0) , (4,-3) , (5,0) , (-1,4) , (-3,3) , (-4,2) , (-5,1) , (-4,-3) ] 

如果有人在任何地方发现任何错误，请回答

Answer 1

叉积“按原样”仅给出角度的符号，因为您的向量未标准化（单位长度）。向量大小的除法是朝正确方向迈出的一步，但可以提供可能的角度范围-Pi/2..Pi/2

您可以获得可比较的值-使用-Pi..Pi在整个范围atan2中的角度

angle = atan2(x1 * y2 - x2 * y1, x1 * x2 + y1 * y2);