:heavy_check_mark: 偏角ソート (Geometry/arg_sort.hpp)

偏角ソート（整数演算）

2 次元ベクトル $(x, y)$ を偏角 $\theta = \mathrm{atan2}(y, x)$ の昇順（範囲 $(-\pi, \pi]$）でソートするための比較関数です。
浮動小数点演算を使用せず、符号判定と外積（クロス積）だけで順序を定めます。

  • 原点 $(0,0)$ は $\theta = 0$ とみなし、グループ 0 として扱います。
  • 同じ偏角の点同士の順序は任意です（cross == 0 のときは同値扱い）。

関数 

bool arg_comp(const pair<long long, long long> &p,
              const pair<long long, long long> &q)

p と q を偏角順（$(-\pi,\pi]$ の昇順）に比較し、p が q より先なら true を返します。

計算量

  • 1 回の比較は $O(1)$
  • ソート全体は $O(N \log N)$

参考

Verified with

Code 

#include <bits/stdc++.h>
using namespace std;

bool arg_comp(const pair<long long, long long> &p, const pair<long long, long long> &q)
{
    // (-pi, pi] の偏角順にするための分類：
    //  -1: theta <= 0（下半平面 + 正のx軸）
    //   0: 原点（角度0扱い）
    //  +1: theta > 0（上半平面 + 負のx軸(=pi)）
    auto sign = [](const pair<long long, long long> &p) -> int
    {
        if (p.first == 0 && p.second == 0)
            return 0;
        else if (p.second < 0 || (p.second <= 0 && p.first > 0))
            return -1;
        else
            return 1;
    };
    const int sp = sign(p), sq = sign(q);
    if (sp != sq)
    {
        return sp < sq;
    }

    // 同一グループ内は外積の符号で偏角順（反時計回りが先）
    auto cross = [](const pair<long long, long long> &p, const pair<long long, long long> &q) -> long long
    {
        return p.first * q.second - p.second * q.first;
    };
    return cross(p, q) > 0;
}

#line 1 "Geometry/arg_sort.hpp"
#include <bits/stdc++.h>
using namespace std;

bool arg_comp(const pair<long long, long long> &p, const pair<long long, long long> &q)
{
    // (-pi, pi] の偏角順にするための分類：
    //  -1: theta <= 0（下半平面 + 正のx軸）
    //   0: 原点（角度0扱い）
    //  +1: theta > 0（上半平面 + 負のx軸(=pi)）
    auto sign = [](const pair<long long, long long> &p) -> int
    {
        if (p.first == 0 && p.second == 0)
            return 0;
        else if (p.second < 0 || (p.second <= 0 && p.first > 0))
            return -1;
        else
            return 1;
    };
    const int sp = sign(p), sq = sign(q);
    if (sp != sq)
    {
        return sp < sq;
    }

    // 同一グループ内は外積の符号で偏角順（反時計回りが先）
    auto cross = [](const pair<long long, long long> &p, const pair<long long, long long> &q) -> long long
    {
        return p.first * q.second - p.second * q.first;
    };
    return cross(p, q) > 0;
}
Back to top page