src/verify/yosupo-sort-points-by-argument.test.cpp

View this file on GitHub
Last update: 2026-01-25 12:55:48+09:00
Problem: https://judge.yosupo.jp/problem/sort_points_by_argument

Depends on

Polar Angle Sort (atan2-compatible) (src/geometry/angularsort.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/sort_points_by_argument"
#include "../../cp-library/angularsort"

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

struct Point {
    int x;
    int y;
    int idx;
};

using cmp = angular_sort::cmp<Point>;

int main() {
    int N;
    cin >> N;
    vector<Point> p(N);
    for (int i = 0; i < N; ++i) {
        int x, y;
        cin >> x >> y;
        p[i] = {x, y, i};
    }
    ranges::sort(p, cmp{});
    for (auto& i : p) {
        cout << i.x << ' ' << i.y << '\n';
    }
    return 0;
}

#line 1 "src/verify/yosupo-sort-points-by-argument.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/sort_points_by_argument"
#line 2 "src/geometry/angularsort.hpp"

namespace akTARDIGRADE13::angular_sort {

namespace detail {

template <typename Point>
constexpr bool is_lower(const Point& a) {
    return (a.y < 0) || (a.y == 0 && a.x > 0);
}

template <typename Point, typename BigInt>
constexpr BigInt cross(const Point& a, const Point& b) {
    return (BigInt)a.x * (BigInt)b.y - (BigInt)a.y * (BigInt)b.x;
}

template <typename Point, typename BigInt>
constexpr BigInt norm2(const Point& a) {
    return (BigInt)a.x * (BigInt)a.x + (BigInt)a.y * (BigInt)a.y;
}

} // namespace detail

/**
 * @brief Polar Angle Sort (atan2-compatible)
 *
 * @details
 * 点（ベクトル）を原点からの偏角に基づいて並べるための比較器。
 * 並び順は各点 p=(x,y) に対する atan2(y,x) の昇順と同一と考えてよい。
 *
 * ただし実装では atan2 や浮動小数点演算を用いず、
 * 半平面判定と外積により整数演算のみで同じ角度順を実現する。
 *
 * 境界および特別な点の扱い：
 * - 負の x 軸 (x<0, y=0) は角 π として扱う
 * - 原点 (0,0) は atan2(0,0)=0 と定義する（角 0 相当）
 * - 偏角が等しい点同士（同一直線・同方向、原点を含む）は
 *   原点からの距離（二乗ノルム）の昇順でタイブレークする
 *
 * @tparam Point メンバ変数 x, y を持つ点型（整数型を想定）。
 * @tparam BigInt 外積・二乗距離の計算に用いる型（デフォルトは long long）。
 *
 * @note
 * BigInt が小さい場合、座標の大きさによっては外積・二乗距離がオーバーフローし得る。
 *
 * @complexity 比較 1 回あたり O(1)
 */
template <typename Point, typename BigInt = long long>
struct cmp {
    /**
     * @brief a が b より先（偏角が小さい、または同角で距離が短い）なら true。
     *
     * @param a 点 a。
     * @param b 点 b。
     * @return a が b より先なら true。
     *
     * @complexity O(1)
     */
    constexpr bool operator()(const Point& a, const Point& b) const {
        const bool la = detail::is_lower(a);
        const bool lb = detail::is_lower(b);
        if (la != lb) return la;

        const auto cr = detail::cross<Point, BigInt>(a, b);
        if (cr != 0) return cr > 0;

        const auto na = detail::norm2<Point, BigInt>(a);
        const auto nb = detail::norm2<Point, BigInt>(b);
        return na < nb;
    }
};

} // namespace akTARDIGRADE13::angular_sort
#line 3 "src/verify/yosupo-sort-points-by-argument.test.cpp"

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

struct Point {
    int x;
    int y;
    int idx;
};

using cmp = angular_sort::cmp<Point>;

int main() {
    int N;
    cin >> N;
    vector<Point> p(N);
    for (int i = 0; i < N; ++i) {
        int x, y;
        cin >> x >> y;
        p[i] = {x, y, i};
    }
    ranges::sort(p, cmp{});
    for (auto& i : p) {
        cout << i.x << ' ' << i.y << '\n';
    }
    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	all_same_00	AC	192 ms	19 MB
g++	all_same_01	AC	171 ms	19 MB
g++	all_same_02	AC	221 ms	19 MB
g++	example_00	AC	11 ms	18 MB
g++	half_same_00	AC	178 ms	19 MB
g++	half_same_01	AC	204 ms	19 MB
g++	half_same_02	AC	222 ms	19 MB
g++	max_random_00	AC	217 ms	19 MB
g++	max_random_01	AC	217 ms	19 MB
g++	max_random_02	AC	218 ms	19 MB
g++	near_arg_00	AC	227 ms	19 MB
g++	near_arg_01	AC	215 ms	19 MB
g++	near_arg_02	AC	215 ms	19 MB
g++	near_arg_shuffle_00	AC	214 ms	19 MB
g++	near_arg_shuffle_01	AC	216 ms	19 MB
g++	near_arg_shuffle_02	AC	223 ms	19 MB
g++	only_x_axis_00	AC	11 ms	18 MB
g++	random_00	AC	150 ms	20 MB
g++	random_01	AC	167 ms	20 MB
g++	random_02	AC	65 ms	19 MB
g++	small_all_00	AC	11 ms	18 MB