「笔记」极角排序

• 直接计算极角
• 利用叉乘
• CF598C Nearest vectors
• ABC225- E 7
• 鸣谢

极角排序，就是平面上有若干点，选一点作为极点，那么每个点有极坐标 \((\rho ,\theta)\) ，将它们关于极角 \(\theta\) 排序。进行极角排序有两种方法。

直接计算极角

我们知道极坐标和直角坐标转换公式中有 \(\tan \theta = \frac{y}{x}\)，所以可以用 \(\arctan\) 来计算。然而 \(\arctan\) 的值域只有 \((-\frac{\pi}{2},\frac{\pi}{2})\) ，而且当 \(x=0\) 时无定义，所以需要复杂的分类讨论。

所幸 cmath 中有一个 atan2(y,x) 的函数可以直接计算 (x,y) 的极角，值域是 \((-\pi, \pi]\)，所以可以直接用，只不过需要留心第四象限的极角会比第一象限小。

using Points = vector;
double theta(auto p) { return atan2(p.y, p.x); } // 求极角
void psort(Points &ps, Point c = O)              // 极角排序
{
    sort(ps.begin(), ps.end(), [&](auto p1, auto p2) {
        return lt(theta(p1 - c), theta(p2 - c));
    });
}

如果想减少常数，可以提前算出每个点的极角。

利用叉乘

叉乘的正负遵循右手定则，按旋转方向弯曲右手四指，则若拇指向上叉乘为正，拇指向下叉乘为负。也就是说，如果一个向量通过劣角旋转到另一个向量的方向需要按逆时针方向，那么叉乘为正，否则叉乘为负。

仅靠叉乘是不能进行排序的，因为它不符合偏序关系的条件。如果定义 \(\vec{x} \times \vec{y} < 0\) 则 \(\theta_{\vec{x}} < \theta_{\vec{y}}\)，那么我们会发现通过不断在坐标轴上旋转，一个向量的极角最终会小于自己。但是在同一象限内计算叉乘是可以的，所以我们先比较象限再做叉乘。

int qua(auto p) { return lt(p.y, 0) << 1 | lt(p.x, 0) ^ lt(p.y, 0); }    // 求象限
void psort(Points &ps, Point c = O)                               // 极角排序
{
    sort(ps.begin(), ps.end(), [&](auto v1, auto v2) {
        return qua(v1 - c) < qua(v2 - c) || qua(v1 - c) == qua(v2 - c) && lt(cross(v1 - c, v2 - c), 0);
    });
}

我们用0、1、2、3来表示第一、二、三、四象限。

这种方法常数可能稍微大一点，但是精度比较好，如果坐标都是整数的话是完全没有精度损失的。

CF598C Nearest vectors

直接用 atan2 函数算出每个点的极角，然后按照极角从小到大排序，依次比较相邻两个点的差值取最优。

/*
Work by: Suzt_ilymtics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include
#include
#include
#include
#include
#include
#define LL long long
#define LD long double
#define orz cout<<"lkp AK IOI!"<

/*
Work by: Suzt_ilymtics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include
#include
#include
#include
#include
#include
#define LL long long
#define LD long double
#define orz cout<<"lkp AK IOI!"<= lst) {
            ans ++, lst = a[i].r;
        }
    }
    printf("%d", ans);
    return 0;
}