点を原点から見た角度の順に並べる（偏角ソート）

点を「原点から見た向き」の順に並べること。
距離は関係なく、x 軸の正の向きから反時計回りに何度回った位置にあるか（偏角）で並べます。

使う場面

• 原点を通る直線・半平面に入る点を数える（ABC481 E）
• ある点を中心に、周りの点を角度順に見ていく（角度のスイープ）
• 凸包（Graham scan）、多角形の頂点を順番に並べる
• 「原点を含む三角形の個数」などの数え上げ

コード例1 atan2 を使う（簡単だが精度に注意）

sort(p.begin(), p.end(), [](const P& a, const P& b) {
  return atan2l(a.y, a.x) < atan2l(b.y, b.x);
});

• atan2(y,x) は偏角を \( ( – \pi, \pi] \) で返す。順番は「左下（\( -180^\circ \)の直度） → 下 → 右 → 上 → 左」。
• 座標が大きいと誤判定する。座標が \( 10^9 \) までだと、\( 2 \) 点の偏角の差が \( 10^{-18} \) くらいになることがあり、double どころか long double でも区別できない。
• 座標が小さい問題や、多少ずれても答えに影響しない問題なら使える。

コード例2 半分に分けてから外積（整数だけで正確）

まず平面を \( 2 \) つに分け、同じ側どうしのときだけ外積で比べる。
同じ側の \( 2 \) 点は \( 180^\circ \) 未満しか離れていないので、外積が正しく働く。

        上半分（half = 0）
          0° ≦ 偏角 < 180°
  ───────────●────────── x 軸
          180° ≦ 偏角 < 360°
        下半分（half = 1）

  x 軸の正の部分（0°）は上半分、負の部分（180°）は下半分に入れる

\( x \) 軸の正の部分 \( (0^\circ ) \) は上半分、負の部分 \( (180^\circ ) \) は下半分に入れる。

struct P { ll x, y; }

ll cross(const P& a, const P& b) { return a.x * b.y - a.y * b.x; }

// 0° <= 偏角 < 180° なら 0, 180° <= 偏角 < 360° なら 1
int half(const P& p) {
  if(0 < p.y || (p.y == 0 && 0 < p.x) {
    return 0;
  } else {
    return 1;
  }
}

bool arg_less(const P& a, const P& b) {
  if(half(a) != half(b)) {
    return half(a) < half(b);
  } else {
    return 0 < cross(a, b);
  }
}

sort(p.begin(), p.end(), arg_less);

これで \( (0^\circ ) \) から反時計回りの順に並びます。

• 同じ向きの点 (\(cross == 0\) で同じ側） でも false になり、「等しい」扱い。距離の近い順にもしたいなら、そのときだけ \(x \times x + y \times y\) で比べる。
• 原点 \( 0, 0 \) は向きがないので、入っていたら先に除いておく。

atan2 と同じ順（ \( 180^\circ \) の直後から）にしたいとき

half を変えるだけ。

int half(const P& p){ if(p.y < 0){
  return 0;
  } else {
  return 1;
  }
}

オーバーフローの目安

long long 上限は約 \( 9.2 \times 10^{18} \) 。

ソートしたあと：円環としてしゃくとり

偏角は一周するので、「ある角度の範囲に入る点」を数えるときは、配列を \(2\) 周分あると思って添字を \(% n\) で回す。

// 各 i について、偏角が [θi, θi + 180°) の点の個数
int r = 0;
for (int i = 0; i < n; i++) {
    r = max(r, i + 1);
    while (r < i + n && cross(p[i], p[r % n]) > 0) r++;
    // r - i 個が入っている
}

• \(r < i + n\) を忘れると、全部の点が入るときに止まらない。
• 同じ向きの点があり得る問題では、 cross == 0 の扱い（\( 180^\circ \) ちょうどの点、同じ向きの点）を別に考える。