Submit Info #48763

Problem Lang User Status Time Memory
Sort Points by Argument cpp wleungBVG AC 393 ms 10.81 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.67 MiB
max_random_00 AC 387 ms 10.81 MiB
max_random_01 AC 389 ms 10.77 MiB
max_random_02 AC 393 ms 10.72 MiB
near_arg_00 AC 386 ms 10.59 MiB
near_arg_01 AC 386 ms 10.59 MiB
near_arg_02 AC 382 ms 10.63 MiB
near_arg_shuffle_00 AC 383 ms 10.55 MiB
near_arg_shuffle_01 AC 387 ms 10.55 MiB
near_arg_shuffle_02 AC 385 ms 10.55 MiB
only_x_axis_00 AC 1 ms 0.71 MiB
random_00 AC 252 ms 7.05 MiB
random_01 AC 291 ms 8.30 MiB
random_02 AC 103 ms 3.33 MiB
small_all_00 AC 1 ms 0.68 MiB

// https://judge.yosupo.jp/problem/sort_points_by_argument #include <bits/stdc++.h> using namespace std; template<class C>constexpr int sz(const C&c){return int(c.size());} using ll=long long;using ld=long double;constexpr const char nl='\n',sp=' '; using T = long double; constexpr const T EPS = 1e-9; bool lt(T a, T b) { return a + EPS < b; } bool le(T a, T b) { return !lt(b, a); } bool gt(T a, T b) { return lt(b, a); } bool ge(T a, T b) { return !lt(a, b); } bool eq(T a, T b) { return !lt(a, b) && !lt(b, a); } bool ne(T a, T b) { return lt(a, b) || lt(b, a); } int sgn(T a) { return lt(a, 0) ? -1 : lt(0, a) ? 1 : 0; } struct eps_lt { bool operator () (T a, T b) const { return lt(a, b); } }; struct eps_le { bool operator () (T a, T b) const { return !lt(b, a); } }; struct eps_gt { bool operator () (T a, T b) const { return lt(b, a); } }; struct eps_ge { bool operator () (T a, T b) const { return !lt(a, b); } }; struct eps_eq { bool operator () (T a, T b) const { return !lt(a, b) && !lt(b, a); } }; struct eps_ne { bool operator () (T a, T b) const { return lt(a, b) || lt(b, a); } }; #define OP(op, U, a, x, y) pt operator op (U a) const { return pt(x, y); } \ pt &operator op##= (U a) { return *this = *this op a; } #define CMP(op, body) bool operator op (pt p) const { return body; } struct pt { T x, y; constexpr pt(T x = 0, T y = 0) : x(x), y(y) {} pt operator + () const { return *this; } pt operator - () const { return pt(-x, -y); } OP(+, pt, p, x + p.x, y + p.y) OP(-, pt, p, x - p.x, y - p.y) OP(*, T, a, x * a, y * a) OP(/, T, a, x / a, y / a) friend pt operator * (T a, pt p) { return pt(a * p.x, a * p.y); } bool operator < (pt p) const { return eq(x, p.x) ? lt(y, p.y) : lt(x, p.x); } CMP(<=, !(p < *this)) CMP(>, p < *this) CMP(>=, !(*this < p)) CMP(==, !(*this < p) && !(p < *this)) CMP(!=, *this < p || p < *this) OP(*, pt, p, x * p.x - y * p.y, y * p.x + x * p.y) OP(/, pt, p, (x * p.x + y * p.y) / (p.x * p.x + p.y * p.y), (y * p.x - x * p.y) / (p.x * p.x + p.y * p.y)) }; #undef OP #undef CMP istream &operator >> (istream &stream, pt &p) { return stream >> p.x >> p.y; } ostream &operator << (ostream &stream, pt p) { return stream << p.x << ' ' << p.y; } pt conj(pt a) { return pt(a.x, -a.y); } T dot(pt a, pt b) { return a.x * b.x + a.y * b.y; } T cross(pt a, pt b) { return a.x * b.y - a.y * b.x; } T norm(pt a) { return dot(a, a); } T abs(pt a) { return sqrt(norm(a)); } T arg(pt a) { return atan2(a.y, a.x); } pt polar(T r, T theta) { return r * pt(cos(theta), sin(theta)); } T distSq(pt a, pt b) { return norm(b - a); } T dist(pt a, pt b) { return abs(b - a); } T ang(pt a, pt b) { return arg(b - a); } // sign of ang, area2, ccw: 1 if counterclockwise, 0 if collinear, // -1 if clockwise T ang(pt a, pt b, pt c) { a -= b; c -= b; return remainder(atan2(a.y, a.x) - atan2(c.y, c.x), 2 * acos(T(-1))); } // twice the signed area of triangle a, b, c T area2(pt a, pt b, pt c) { return cross(b - a, c - a); } int ccw(pt a, pt b, pt c) { return sgn(area2(a, b, c)); } // a rotated theta radians around p pt rot(pt a, pt p, T theta) { return (a - p) * pt(polar(T(1), theta)) + p; } // rotated 90 degrees ccw pt perp(pt a) { return pt(-a.y, a.x); } #define OP(op, body) Angle operator op (Angle a) const { return body; } \ Angle &operator op##= (Angle a) { return *this = *this op a; } #define CMP(op, body) bool operator op (Angle a) const { return body; } struct Angle { static pt pivot; static void setPivot(pt p) { pivot = p; } pt p; Angle(pt p = pt(0, 0)) : p(p) {} int half() const { if (eq(p.x, pivot.x) && eq(p.y, pivot.y)) return 2; return int(!lt(p.y, pivot.y) && (!eq(p.y, pivot.y) || !lt(p.x, pivot.x))); } bool operator < (Angle a) const { int h = half() - a.half(); return h == 0 ? ccw(pivot, p, a.p) > 0 : h < 0; } CMP(<=, !(a < *this)) CMP(>, a < *this) CMP(>=, !(*this < a)) CMP(==, !(*this < a) && !(a < *this)) CMP(!=, *this < a || a < *this) Angle operator + () const { return *this; } Angle operator - () const { return Angle(conj(p)); } OP(+, Angle(pivot + (p - pivot) * (a.p - pivot))) OP(-, *this + (-a)) }; #undef OP #undef CMP pt Angle::pivot = pt(0, 0); int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); // freopen("err.txt", "w", stderr); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N; cin >> N; vector<Angle> A(N); for (auto &&a : A) cin >> a.p; sort(A.begin(), A.end()); auto e = equal_range(A.begin(), A.end(), Angle(pt(0, 0))); vector<Angle> zeros(e.first, e.second); A.erase(e.first, e.second); e = equal_range(A.begin(), A.end(), Angle(pt(-1, 0))); vector<Angle> negX(e.first, e.second); A.erase(e.first, e.second); A.insert(lower_bound(A.begin(), A.end(), Angle(pt(1, 0))), zeros.begin(), zeros.end()); A.insert(A.end(), negX.begin(), negX.end()); cout << fixed << setprecision(0); for (auto &&a : A) cout << a.p << nl; return 0; }