CP-Algorithms Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub cp-algorithms/cp-algorithms-aux

:heavy_check_mark: Sort Points by Argument (verify/geometry/arg.test.cpp)

Depends on

Code

// @brief Sort Points by Argument
#define PROBLEM "https://judge.yosupo.jp/problem/sort_points_by_argument"
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("tune=native")
#include "cp-algo/geometry/point.hpp"
#include <bits/stdc++.h>

using namespace std;
using namespace cp_algo::geometry;
using point = point_t<int64_t>;

void solve() {
    int n;
    cin >> n;
    vector<point> pts(n);
    for(auto &r: pts) {
        r.read();
    }
    ranges::sort(pts, point::ccw_abs);
    for(auto r: pts) {
        r.print();
    }
}

signed main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) {
        solve();
    }
}
#line 1 "verify/geometry/arg.test.cpp"
// @brief Sort Points by Argument
#define PROBLEM "https://judge.yosupo.jp/problem/sort_points_by_argument"
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("tune=native")
#line 1 "cp-algo/geometry/point.hpp"


#line 1 "cp-algo/random/rng.hpp"


#include <chrono>
#include <random>
namespace cp_algo::random {
    uint64_t rng() {
        static std::mt19937_64 rng(
            std::chrono::steady_clock::now().time_since_epoch().count()
        );
        return rng();
    }
}

#line 4 "cp-algo/geometry/point.hpp"
#include <iostream>
#include <complex>
namespace cp_algo::geometry {
    template<typename ftype>
    struct point_t: public std::complex<ftype> {
        using Base = std::complex<ftype>;
        using Base::Base;

        point_t(Base const& t): Base(t) {}
        
        auto operator <=> (point_t const& t) const {
            return std::pair{y(), -x()} <=> std::pair{t.y(), -t.x()};
        }

        ftype x() const {return Base::real();}
        ftype y() const {return Base::imag();}

        point_t cmul(point_t const& t) const {return conj(*this) * t;}
        ftype dot(point_t const& t) const {return cmul(t).x();}
        ftype cross(point_t const& t) const {return cmul(t).y();}

        static constexpr point_t O = {0, 0};

        int half() const {
            return *this < O ? -1 : *this == O ? 0 : 1;
        }

        static bool ccw(point_t const& a, point_t const& b) {
            return a.cross(b) > 0;
        }
        static bool ccw_abs(point_t const& a, point_t const & b) {
            return std::tuple{a.half(), (ftype)0, norm(a)} <
                   std::tuple{b.half(), a.cross(b), norm(b)};
        }
        void read() {
            ftype _x, _y;
            std::cin >> _x >> _y;
            *this = {_x, _y};
        }
        void print() const {
            std::cout << x() << ' ' << y() << "\n";
        }
    };
}

#line 6 "verify/geometry/arg.test.cpp"
#include <bits/stdc++.h>

using namespace std;
using namespace cp_algo::geometry;
using point = point_t<int64_t>;

void solve() {
    int n;
    cin >> n;
    vector<point> pts(n);
    for(auto &r: pts) {
        r.read();
    }
    ranges::sort(pts, point::ccw_abs);
    for(auto r: pts) {
        r.print();
    }
}

signed main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) {
        solve();
    }
}

Test cases

Env Name Status Elapsed Memory
g++ all_same_00 :heavy_check_mark: AC 45 ms 6 MB
g++ all_same_01 :heavy_check_mark: AC 52 ms 6 MB
g++ all_same_02 :heavy_check_mark: AC 56 ms 6 MB
g++ example_00 :heavy_check_mark: AC 6 ms 4 MB
g++ half_same_00 :heavy_check_mark: AC 67 ms 6 MB
g++ half_same_01 :heavy_check_mark: AC 71 ms 6 MB
g++ half_same_02 :heavy_check_mark: AC 76 ms 6 MB
g++ max_random_00 :heavy_check_mark: AC 84 ms 6 MB
g++ max_random_01 :heavy_check_mark: AC 83 ms 6 MB
g++ max_random_02 :heavy_check_mark: AC 82 ms 6 MB
g++ near_arg_00 :heavy_check_mark: AC 79 ms 6 MB
g++ near_arg_01 :heavy_check_mark: AC 85 ms 6 MB
g++ near_arg_02 :heavy_check_mark: AC 83 ms 6 MB
g++ near_arg_shuffle_00 :heavy_check_mark: AC 82 ms 6 MB
g++ near_arg_shuffle_01 :heavy_check_mark: AC 80 ms 6 MB
g++ near_arg_shuffle_02 :heavy_check_mark: AC 79 ms 6 MB
g++ only_x_axis_00 :heavy_check_mark: AC 6 ms 3 MB
g++ random_00 :heavy_check_mark: AC 52 ms 5 MB
g++ random_01 :heavy_check_mark: AC 61 ms 6 MB
g++ random_02 :heavy_check_mark: AC 26 ms 4 MB
g++ small_all_00 :heavy_check_mark: AC 6 ms 4 MB
Back to top page