test/Geometry/arg_sort/yosupo-sort_points_by_argument.cpp

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

Depends on

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

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/sort_points_by_argument

#include "Geometry/arg_sort.hpp"
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int N;
    cin >> N;

    vector<pair<long long, long long>> XY(N);

    for (int i = 0; i < N; i++)
    {
        cin >> XY[i].first >> XY[i].second;
    }

    sort(XY.begin(), XY.end(), arg_comp);

    for (int i = 0; i < N; i++)
    {
        cout << XY[i].first << " " << XY[i].second << endl;
    }

    return 0;
}

#line 1 "test/Geometry/arg_sort/yosupo-sort_points_by_argument.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/sort_points_by_argument

#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;
}
#line 5 "test/Geometry/arg_sort/yosupo-sort_points_by_argument.cpp"

using namespace std;

int main()
{
    int N;
    cin >> N;

    vector<pair<long long, long long>> XY(N);

    for (int i = 0; i < N; i++)
    {
        cin >> XY[i].first >> XY[i].second;
    }

    sort(XY.begin(), XY.end(), arg_comp);

    for (int i = 0; i < N; i++)
    {
        cout << XY[i].first << " " << XY[i].second << endl;
    }

    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	all_same_00	AC	195 ms	6 MB
g++	all_same_01	AC	250 ms	6 MB
g++	all_same_02	AC	294 ms	6 MB
g++	example_00	AC	5 ms	3 MB
g++	half_same_00	AC	281 ms	6 MB
g++	half_same_01	AC	281 ms	6 MB
g++	half_same_02	AC	290 ms	6 MB
g++	max_random_00	AC	301 ms	6 MB
g++	max_random_01	AC	304 ms	6 MB
g++	max_random_02	AC	307 ms	6 MB
g++	near_arg_00	AC	299 ms	6 MB
g++	near_arg_01	AC	299 ms	6 MB
g++	near_arg_02	AC	298 ms	6 MB
g++	near_arg_shuffle_00	AC	314 ms	6 MB
g++	near_arg_shuffle_01	AC	298 ms	6 MB
g++	near_arg_shuffle_02	AC	303 ms	6 MB
g++	only_x_axis_00	AC	5 ms	3 MB
g++	random_00	AC	193 ms	5 MB
g++	random_01	AC	230 ms	6 MB
g++	random_02	AC	84 ms	4 MB
g++	small_all_00	AC	5 ms	3 MB