verify/sort_points_by_argument.test.cpp

View this file on GitHub · Last update: 2026-07-25 04:22:18-07:00

Problem: https://judge.yosupo.jp/problem/sort_points_by_argument

Depends on

• geometry/point.hpp

Code

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

#include <bits/stdc++.h>
#include <cassert>

#include "geometry/point.hpp"

int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr);

	using pt_t = Point<int, int64_t>;

	int N; std::cin >> N;
	std::vector<pt_t> P(N);
	for (auto& p : P) std::cin >> p;
	auto fix_0 = [&](pt_t p) -> pt_t { return p == pt_t(0, 0) ? pt_t(1, 0) : p; };
	auto cmp = angle_cmp_upto(pt_t(-1, 0));
	std::ranges::sort(P, [&](auto a, auto b) -> bool { return cmp(fix_0(a), fix_0(b)); });
	for (auto p : P) {
		std::cout << p.x << ' ' << p.y << '\n';
	}

	return 0;
}

#include <bits/stdc++.h>
#line 1 "verify/sort_points_by_argument.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/sort_points_by_argument

#line 5 "verify/sort_points_by_argument.test.cpp"

#line 2 "src/geometry/point.hpp"

#line 7 "src/geometry/point.hpp"

template <typename T, typename AreaT=T> struct Point {
public:
	T x, y;
	Point() : x(0), y(0) {}
	Point(T x_, T y_) : x(x_), y(y_) {}
	template <typename U, typename V> explicit Point(const Point<U, V>& p) : x(p.x), y(p.y) {}
	Point(const std::pair<T, T>& p) : x(p.first), y(p.second) {}
	Point(const std::complex<T>& p) : x(real(p)), y(imag(p)) {}
	explicit operator std::pair<T, T> () const { return std::pair<T, T>(x, y); }
	explicit operator std::complex<T> () const { return std::complex<T>(x, y); }
	auto as_pair() const { return std::pair<T, T>(*this); }
	auto as_complex() const { return std::complex<T>(*this); }

	friend std::ostream& operator << (std::ostream& o, const Point& p) { return o << '(' << p.x << ',' << p.y << ')'; }
	friend std::istream& operator >> (std::istream& i, Point& p) { return i >> p.x >> p.y; }
	friend bool operator == (const Point& a, const Point& b) { return a.x == b.x && a.y == b.y; }
	friend bool operator != (const Point& a, const Point& b) { return !(a==b); }

	Point operator + () const { return Point(+x, +y); }
	Point operator - () const { return Point(-x, -y); }

	Point& operator += (const Point& p) { x += p.x, y += p.y; return *this; }
	Point& operator -= (const Point& p) { x -= p.x, y -= p.y; return *this; }
	Point& operator *= (const T& t) { x *= t, y *= t; return *this; }
	Point& operator /= (const T& t) { x /= t, y /= t; return *this; }

	friend Point operator + (const Point& a, const Point& b) { return Point(a.x+b.x, a.y+b.y); }
	friend Point operator - (const Point& a, const Point& b) { return Point(a.x-b.x, a.y-b.y); }
	friend Point operator * (const Point& a, const T& t) { return Point(a.x*t, a.y*t); }
	friend Point operator * (const T& t ,const Point& a) { return Point(t*a.x, t*a.y); }
	friend Point operator / (const Point& a, const T& t) { return Point(a.x/t, a.y/t); }

	AreaT dist2() const { return AreaT(x) * AreaT(x) + AreaT(y) * AreaT(y); }
	auto dist() const { return std::sqrt(dist2()); }
	Point unit() const { return *this / this->dist(); }
	auto angle() const { return std::atan2(y, x); }

	T int_norm() const { return std::gcd(x,y); }
	Point int_unit() const { if (!x && !y) return *this; return *this / this->int_norm(); }

	// Convenient free-functions, mostly for generic interop
	friend auto norm(const Point& a) { return a.dist2(); }
	friend auto abs(const Point& a) { return a.dist(); }
	friend auto unit(const Point& a) { return a.unit(); }
	friend auto arg(const Point& a) { return a.angle(); }
	friend auto int_norm(const Point& a) { return a.int_norm(); }
	friend auto int_unit(const Point& a) { return a.int_unit(); }

	Point perp_cw() const { return Point(y, -x); }
	Point perp_ccw() const { return Point(-y, x); }

	friend AreaT dot(const Point& a, const Point& b) { return AreaT(a.x) * AreaT(b.x) + AreaT(a.y) * AreaT(b.y); }
	friend AreaT cross(const Point& a, const Point& b) { return AreaT(a.x) * AreaT(b.y) - AreaT(a.y) * AreaT(b.x); }
	friend AreaT cross3(const Point& a, const Point& b, const Point& c) { return cross(b-a, c-a); }

	// Complex numbers and rotation
	friend Point conj(const Point& a) { return Point(a.x, -a.y); }

	// Returns conj(a) * b
	friend Point dot_cross(const Point& a, const Point& b) { return Point(dot(a, b), cross(a, b)); }
	friend Point cmul(const Point& a, const Point& b) { return dot_cross(conj(a), b); }
	friend Point cdiv(const Point& a, const Point& b) { return dot_cross(b, a) / b.dist2(); }

	// Must be a unit vector; otherwise multiplies the result by abs(u)
	Point rotate(const Point& u) const { return dot_cross(conj(u), *this); }
	Point unrotate(const Point& u) const { return dot_cross(u, *this); }

	friend bool lex_less(const Point& a, const Point& b) {
		return std::tie(a.x, a.y) < std::tie(b.x, b.y);
	}

	friend bool same_dir(const Point& a, const Point& b) { return cross(a,b) == 0 && dot(a,b) > 0; }

	// check if 180 <= s..t < 360
	friend bool is_reflex(const Point& a, const Point& b) { auto c = cross(a,b); return c ? (c < 0) : (dot(a, b) < 0); }

	// operator < (s,t) for angles in [base,base+2pi)
	friend bool angle_less_from(const Point& base, const Point& s, const Point& t) {
		int r = is_reflex(base, s) - is_reflex(base, t);
		return r ? (r < 0) : (0 < cross(s, t));
	}
	// operator < (s,t) for angles in (base,base+2pi]
	friend bool angle_less_upto(const Point& base, const Point& s, const Point& t) {
		int r = is_reflex(t, base) - is_reflex(s, base);
		return r ? (r < 0) : (0 < cross(s, t));
	}

	friend auto angle_cmp_from(const Point& base) {
		return [base](const Point& s, const Point& t) { return angle_less_from(base, s, t); };
	}
	friend auto angle_cmp_upto(const Point& base) {
		return [base](const Point& s, const Point& t) { return angle_less_upto(base, s, t); };
	}
	friend auto angle_cmp_center_from(const Point& center, const Point& dir) {
		return [center, dir](const Point& s, const Point& t) -> bool { return angle_less_from(dir, s-center, t-center); };
	}
	friend auto angle_cmp_center_upto(const Point& center, const Point& dir) {
		return [center, dir](const Point& s, const Point& t) -> bool { return angle_less_upto(dir, s-center, t-center); };
	}

	// is p in [s,t] taken ccw? 1/0/-1 for in/border/out
	friend int angle_between(const Point& s, const Point& t, const Point& p) {
		if (same_dir(p, s) || same_dir(p, t)) return 0;
		return angle_less_from(s, p, t) ? 1 : -1;
	}
};
#line 7 "verify/sort_points_by_argument.test.cpp"

int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr);

	using pt_t = Point<int, int64_t>;

	int N; std::cin >> N;
	std::vector<pt_t> P(N);
	for (auto& p : P) std::cin >> p;
	auto fix_0 = [&](pt_t p) -> pt_t { return p == pt_t(0, 0) ? pt_t(1, 0) : p; };
	auto cmp = angle_cmp_upto(pt_t(-1, 0));
	std::ranges::sort(P, [&](auto a, auto b) -> bool { return cmp(fix_0(a), fix_0(b)); });
	for (auto p : P) {
		std::cout << p.x << ' ' << p.y << '\n';
	}

	return 0;
}

// clang-format off
// @formatter:off
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wpragmas"
#pragma GCC diagnostic ignored "-Wunknown-warning-option"
#pragma GCC diagnostic ignored "-Wmisleading-indentation"
#pragma GCC diagnostic ignored "-Wmultistatement-macros"
#include <bits/stdc++.h>
// src/geometry/point.hpp
template<typename T,typename AreaT=T>struct Point{
public:
T x,y;
Point():x(0),y(0){}
Point(T x_,T y_):x(x_),y(y_){}
template<typename U,typename V>explicit Point(const Point<U,V>&p):x(p.x),y(p.y){}
Point(const std::pair<T,T>&p):x(p.first),y(p.second){}
Point(const std::complex<T>&p):x(real(p)),y(imag(p)){}
explicit operator std::pair<T,T>()const{return std::pair<T,T>(x,y);}
explicit operator std::complex<T>()const{return std::complex<T>(x,y);}
auto as_pair()const{return std::pair<T,T>(*this);}
auto as_complex()const{return std::complex<T>(*this);}
friend std::ostream&operator<<(std::ostream&o,const Point&p){return o<<'('<<p.x<<','<<p.y<<')';}
friend std::istream&operator>>(std::istream&i,Point&p){return i>>p.x>>p.y;}
friend bool operator==(const Point&a,const Point&b){return a.x==b.x&&a.y==b.y;}
friend bool operator!=(const Point&a,const Point&b){return!(a==b);}
Point operator+()const{return Point(+x,+y);}
Point operator-()const{return Point(-x,-y);}
Point&operator+=(const Point&p){x+=p.x,y+=p.y;return*this;}
Point&operator-=(const Point&p){x-=p.x,y-=p.y;return*this;}
Point&operator*=(const T&t){x*=t,y*=t;return*this;}
Point&operator/=(const T&t){x/=t,y/=t;return*this;}
friend Point operator+(const Point&a,const Point&b){return Point(a.x+b.x,a.y+b.y);}
friend Point operator-(const Point&a,const Point&b){return Point(a.x-b.x,a.y-b.y);}
friend Point operator*(const Point&a,const T&t){return Point(a.x*t,a.y*t);}
friend Point operator*(const T&t,const Point&a){return Point(t*a.x,t*a.y);}
friend Point operator/(const Point&a,const T&t){return Point(a.x/t,a.y/t);}
AreaT dist2()const{return AreaT(x)*AreaT(x)+AreaT(y)*AreaT(y);}
auto dist()const{return std::sqrt(dist2());}
Point unit()const{return*this/this->dist();}
auto angle()const{return std::atan2(y,x);}
T int_norm()const{return std::gcd(x,y);}
Point int_unit()const{if(!x&&!y)return*this;return*this/this->int_norm();}
friend auto norm(const Point&a){return a.dist2();}
friend auto abs(const Point&a){return a.dist();}
friend auto unit(const Point&a){return a.unit();}
friend auto arg(const Point&a){return a.angle();}
friend auto int_norm(const Point&a){return a.int_norm();}
friend auto int_unit(const Point&a){return a.int_unit();}
Point perp_cw()const{return Point(y,-x);}
Point perp_ccw()const{return Point(-y,x);}
friend AreaT dot(const Point&a,const Point&b){return AreaT(a.x)*AreaT(b.x)+AreaT(a.y)*AreaT(b.y);}
friend AreaT cross(const Point&a,const Point&b){return AreaT(a.x)*AreaT(b.y)-AreaT(a.y)*AreaT(b.x);}
friend AreaT cross3(const Point&a,const Point&b,const Point&c){return cross(b-a,c-a);}
friend Point conj(const Point&a){return Point(a.x,-a.y);}
friend Point dot_cross(const Point&a,const Point&b){return Point(dot(a,b),cross(a,b));}
friend Point cmul(const Point&a,const Point&b){return dot_cross(conj(a),b);}
friend Point cdiv(const Point&a,const Point&b){return dot_cross(b,a)/b.dist2();}
Point rotate(const Point&u)const{return dot_cross(conj(u),*this);}
Point unrotate(const Point&u)const{return dot_cross(u,*this);}
friend bool lex_less(const Point&a,const Point&b){
return std::tie(a.x,a.y)<std::tie(b.x,b.y);
}
friend bool same_dir(const Point&a,const Point&b){return cross(a,b)==0&&dot(a,b)>0;}
friend bool is_reflex(const Point&a,const Point&b){auto c=cross(a,b);return c?(c<0):(dot(a,b)<0);}
friend bool angle_less_from(const Point&base,const Point&s,const Point&t){
int r=is_reflex(base,s)-is_reflex(base,t);
return r?(r<0):(0<cross(s,t));
}
friend bool angle_less_upto(const Point&base,const Point&s,const Point&t){
int r=is_reflex(t,base)-is_reflex(s,base);
return r?(r<0):(0<cross(s,t));
}
friend auto angle_cmp_from(const Point&base){
return[base](const Point&s,const Point&t){return angle_less_from(base,s,t);};
}
friend auto angle_cmp_upto(const Point&base){
return[base](const Point&s,const Point&t){return angle_less_upto(base,s,t);};
}
friend auto angle_cmp_center_from(const Point&center,const Point&dir){
return[center,dir](const Point&s,const Point&t)->bool{return angle_less_from(dir,s-center,t-center);};
}
friend auto angle_cmp_center_upto(const Point&center,const Point&dir){
return[center,dir](const Point&s,const Point&t)->bool{return angle_less_upto(dir,s-center,t-center);};
}
friend int angle_between(const Point&s,const Point&t,const Point&p){
if(same_dir(p,s)||same_dir(p,t))return 0;
return angle_less_from(s,p,t)?1:-1;
}
};
// verify/sort_points_by_argument.test.cpp
int main(){
std::ios_base::sync_with_stdio(false),std::cin.tie(nullptr);
using pt_t=Point<int,int64_t>;
int N;std::cin>>N;
std::vector<pt_t>P(N);
for(auto&p:P)std::cin>>p;
auto fix_0=[&](pt_t p)->pt_t{return p==pt_t(0,0)?pt_t(1,0):p;};
auto cmp=angle_cmp_upto(pt_t(-1,0));
std::ranges::sort(P,[&](auto a,auto b)->bool{return cmp(fix_0(a),fix_0(b));});
for(auto p:P){
std::cout<<p.x<<' '<<p.y<<'\n';
}
return 0;
}
#pragma GCC diagnostic pop
// clang-format on
// @formatter:on

Test cases

Env	Name	Status	Elapsed	Memory
g++-sanitizer	all_same_00	AC	215 ms	16 MB
g++-sanitizer	all_same_01	AC	219 ms	15 MB
g++-sanitizer	all_same_02	AC	218 ms	15 MB
g++-sanitizer	example_00	AC	15 ms	8 MB
g++-sanitizer	half_same_00	AC	269 ms	15 MB
g++-sanitizer	half_same_01	AC	265 ms	15 MB
g++-sanitizer	half_same_02	AC	262 ms	16 MB
g++-sanitizer	max_random_00	AC	291 ms	16 MB
g++-sanitizer	max_random_01	AC	303 ms	15 MB
g++-sanitizer	max_random_02	AC	291 ms	16 MB
g++-sanitizer	near_arg_00	AC	297 ms	15 MB
g++-sanitizer	near_arg_01	AC	299 ms	15 MB
g++-sanitizer	near_arg_02	AC	303 ms	15 MB
g++-sanitizer	near_arg_shuffle_00	AC	287 ms	16 MB
g++-sanitizer	near_arg_shuffle_01	AC	299 ms	15 MB
g++-sanitizer	near_arg_shuffle_02	AC	310 ms	15 MB
g++-sanitizer	only_x_axis_00	AC	13 ms	9 MB
g++-sanitizer	random_00	AC	213 ms	14 MB
g++-sanitizer	random_01	AC	226 ms	15 MB
g++-sanitizer	random_02	AC	85 ms	14 MB
g++-sanitizer	small_all_00	AC	16 ms	9 MB
g++	all_same_00	AC	41 ms	5 MB
g++	all_same_01	AC	51 ms	5 MB
g++	all_same_02	AC	56 ms	5 MB
g++	example_00	AC	3 ms	4 MB
g++	half_same_00	AC	58 ms	5 MB
g++	half_same_01	AC	68 ms	5 MB
g++	half_same_02	AC	65 ms	5 MB
g++	max_random_00	AC	71 ms	5 MB
g++	max_random_01	AC	71 ms	5 MB
g++	max_random_02	AC	73 ms	5 MB
g++	near_arg_00	AC	72 ms	5 MB
g++	near_arg_01	AC	74 ms	5 MB
g++	near_arg_02	AC	73 ms	5 MB
g++	near_arg_shuffle_00	AC	74 ms	5 MB
g++	near_arg_shuffle_01	AC	79 ms	5 MB
g++	near_arg_shuffle_02	AC	78 ms	5 MB
g++	only_x_axis_00	AC	3 ms	4 MB
g++	random_00	AC	48 ms	4 MB
g++	random_01	AC	58 ms	5 MB
g++	random_02	AC	21 ms	4 MB
g++	small_all_00	AC	3 ms	4 MB

Back to top page