This documentation is automatically generated by competitive-verifier/competitive-verifier
// @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();
}
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | all_same_00 | AC | 45 ms | 6 MB |
g++ | all_same_01 | AC | 52 ms | 6 MB |
g++ | all_same_02 | AC | 56 ms | 6 MB |
g++ | example_00 | AC | 6 ms | 4 MB |
g++ | half_same_00 | AC | 67 ms | 6 MB |
g++ | half_same_01 | AC | 71 ms | 6 MB |
g++ | half_same_02 | AC | 76 ms | 6 MB |
g++ | max_random_00 | AC | 84 ms | 6 MB |
g++ | max_random_01 | AC | 83 ms | 6 MB |
g++ | max_random_02 | AC | 82 ms | 6 MB |
g++ | near_arg_00 | AC | 79 ms | 6 MB |
g++ | near_arg_01 | AC | 85 ms | 6 MB |
g++ | near_arg_02 | AC | 83 ms | 6 MB |
g++ | near_arg_shuffle_00 | AC | 82 ms | 6 MB |
g++ | near_arg_shuffle_01 | AC | 80 ms | 6 MB |
g++ | near_arg_shuffle_02 | AC | 79 ms | 6 MB |
g++ | only_x_axis_00 | AC | 6 ms | 3 MB |
g++ | random_00 | AC | 52 ms | 5 MB |
g++ | random_01 | AC | 61 ms | 6 MB |
g++ | random_02 | AC | 26 ms | 4 MB |
g++ | small_all_00 | AC | 6 ms | 4 MB |