Yosupo Library Checker - Sort Points by Argument

偏角ソートの verify

• 問題へのリンク

問題概要

二次元平面上に 個の点が与えられる。各点の座標は である。これらの点を偏角 ( とする) が小さい順にソートせよ。

ただし、点 の偏角は であるとする。また、偏角が等しい点の順序は問わない。

制約

• 
• 

考えたこと

とにかく誤差が怖い問題。各点の座標値の絶対値が まであり得るので、2 点間の角度は 程度の精度まで判別しなければならない。関数 atan2(y, x) を使って、EPS = 1e^18 として偏角ソートしても通ったが、やはり誤差が怖い。

そこで、2 点の比較関数を次のように設計することにした。まず、

• 偏角が負であるもの
• 偏角が 0 であるもの (原点のみ)
• 偏角が正であるもの

という 3 グループ分けてあげて、グループが異なる場合には直ちに大小関係を返す。同じグループ内の 2 点については、外積を用いて偏角の比較することとした。こうすることで、基本的に整数値のみを用いて偏角の比較が可能である。

コード

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

// Point or Vector
template<class DD> struct Point {
    DD x, y;
    Point() {}
    Point(DD x, DD y) : x(x), y(y) {}
};

// 偏角ソート
void arg_sort(vector<Point<long long>> &v) {
    auto sign = [&](const Point<long long> &p) -> int {
        if (p.x == 0 && p.y == 0) return 0;
        else if (p.y < 0 || (p.y <= 0 && p.x > 0)) return -1;
        else return 1;
    };
    auto cmp = [&](const Point<long long> &p, const Point<long long> &q) -> bool {
        return (sign(p) != sign(q) ? sign(p) < sign(q) : p.x * q.y - p.y * q.x > 0);
    };
    sort(v.begin(), v.end(), cmp);
}

void Yosupo_Sort_Points_by_Argument() {
    int N;
    cin >> N;
    vector<Point<long long>> vp(N);
    for (int i = 0; i < N; ++i) cin >> vp[i].x >> vp[i].y;
    arg_sort(vp);
    for (const auto &p : vp) cout << p.x << " " << p.y << endl;
}

int main() {
    Yosupo_Sort_Points_by_Argument();
}