Submit Info #40540

Problem Lang User Status Time Memory
Sort Points by Argument cpp wleungBVG AC 379 ms 10.80 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.67 MiB
max_random_00 AC 379 ms 10.80 MiB
max_random_01 AC 378 ms 10.80 MiB
max_random_02 AC 378 ms 10.74 MiB
near_arg_00 AC 375 ms 10.55 MiB
near_arg_01 AC 375 ms 10.61 MiB
near_arg_02 AC 374 ms 10.61 MiB
near_arg_shuffle_00 AC 374 ms 10.61 MiB
near_arg_shuffle_01 AC 375 ms 10.55 MiB
near_arg_shuffle_02 AC 374 ms 10.61 MiB
random_00 AC 241 ms 7.05 MiB
random_01 AC 284 ms 8.30 MiB
random_02 AC 100 ms 3.30 MiB
small_all_00 AC 1 ms 0.67 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 x real() #define y imag() #define ref const pt & using pt = complex<T>; istream &operator >> (istream &stream, pt &p) { T X, Y; stream >> X >> Y; p = pt(X, Y); return stream; } ostream &operator << (ostream &stream, ref p) { return stream << p.x << ' ' << p.y; } bool operator < (ref a, ref b) { return eq(a.x, b.x) ? lt(a.y, b.y) : lt(a.x, b.x); } bool operator <= (ref a, ref b) { return !(b < a); } bool operator > (ref a, ref b) { return b < a; } bool operator >= (ref a, ref b) { return !(a < b); } bool operator == (ref a, ref b) { return !(a < b) && !(b < a); } bool operator != (ref a, ref b) { return a < b || b < a; } struct pt_lt { bool operator () (ref a, ref b) const { return a < b; } }; struct pt_le { bool operator () (ref a, ref b) const { return !(b < a); } }; struct pt_gt { bool operator () (ref a, ref b) const { return b < a; } }; struct pt_ge { bool operator () (ref a, ref b) const { return !(a < b); } }; struct pt_eq { bool operator () (ref a, ref b) const { return !(a < b) && !(b < a); } }; struct pt_ne { bool operator () (ref a, ref b) const { return a < b || b < a; } }; // abs gets polar distance, arg gets polar angle T dot(ref a, ref b) { return a.x * b.x + a.y * b.y; } T cross(ref a, ref b) { return a.x * b.y - a.y * b.x; } T norm(ref a) { return dot(a, a); } T distSq(ref a, ref b) { return norm(b - a); } T dist(ref a, ref b) { return abs(b - a); } T ang(ref a, ref b) { return arg(b - a); } // sign of ang, area2, ccw: 1 if counterclockwise, 0 if collinear, // -1 if clockwise T ang(ref a, ref b, ref c) { return remainder(ang(b, a) - ang(b, c), 2 * acos(T(-1))); } // twice the signed area of triangle a, b, c T area2(ref a, ref b, ref c) { return cross(b - a, c - a); } int ccw(ref a, ref b, ref c) { return sgn(area2(a, b, c)); } // a rotated theta radians around p pt rot(ref a, ref p, T theta) { return (a - p) * pt(polar(T(1), theta)) + p; } // rotated 90 degrees ccw pt perp(ref a) { return pt(-a.y, a.x); } struct Angle { static pt pivot; static void setPivot(ref p) { pivot = p; } pt p; Angle(ref p = pt(0, 0)) : p(p) {} int half() const { if (eq(p.x, 0) && eq(p.y, 0)) return 2; return int(!lt(p.y, 0) && (!eq(p.y, 0) || !lt(p.x, 0))); } bool operator < (const Angle &a) const { auto p1 = make_pair(half(), (p.y - pivot.y) * (a.p.x - pivot.x)); auto p2 = make_pair(a.half(), (p.x - pivot.x) * (a.p.y - pivot.y)); return p1 < p2; } }; 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; }