#line 2 "/home/user/competitive_programming/library_for_cpp/template/template.hpp" using namespace std; // intrinstic #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include // utility #line 2 "/home/user/competitive_programming/library_for_cpp/template/utility.hpp" using ll = long long; // a ← max(a, b) を実行する. a が更新されたら, 返り値が true. template inline bool chmax(T &a, const U b){ return (a < b ? a = b, 1: 0); } // a ← min(a, b) を実行する. a が更新されたら, 返り値が true. template inline bool chmin(T &a, const U b){ return (a > b ? a = b, 1: 0); } #line 59 "/home/user/competitive_programming/library_for_cpp/template/template.hpp" // math #line 2 "/home/user/competitive_programming/library_for_cpp/template/math.hpp" // 除算に関する関数 // floor(x / y) を求める. template T div_floor(T x, U y){ return (x > 0 ? x / y: (x - y + 1) / y); } // ceil(x / y) を求める. template T div_ceil(T x, U y){ return (x > 0 ? (x + y - 1) / y: x / y) ;} // x を y で割った余りを求める. template T mod(T x, U y){ T q = div_floor(x, y); return x - q * y ; } // x を y で割った商と余りを求める. template pair divmod(T x, U y){ T q = div_floor(x, y); return {q, x - q * y}; } // 四捨五入を求める. template T round(T x, U y){ T q, r; tie (q, r) = divmod(x, y); return (r >= div_ceil(y, 2)) ? q + 1 : q; } // 指数に関する関数 // x の y 乗を求める. ll intpow(ll x, ll y){ ll a = 1; while (y){ if (y & 1) { a *= x; } x *= x; y >>= 1; } return a; } // x の y 乗を z で割った余りを求める. ll modpow(ll x, ll y, ll z){ ll a = 1; while (y){ if (y & 1) { (a *= x) %= z; } (x *= x) %= z; y >>= 1; } return a; } // x の y 乗を z で割った余りを求める. template T modpow(T x, U y, T z) { T a = 1; while (y) { if (y & 1) { (a *= x) %= z; } (x *= x) %= z; y >>= 1; } return a; } // vector の要素の総和を求める. ll sum(vector &X){ ll y = 0; for (auto &&x: X) { y+=x; } return y; } // vector の要素の総和を求める. template T sum(vector &X){ T y = T(0); for (auto &&x: X) { y += x; } return y; } // a x + b y = gcd(a, b) を満たす整数の組 (a, b) に対して, (x, y, gcd(a, b)) を求める. tuple Extended_Euclid(ll a, ll b) { ll s = 1, t = 0, u = 0, v = 1; while (b) { ll q; tie(q, a, b) = make_tuple(div_floor(a, b), b, mod(a, b)); tie(s, t) = make_pair(t, s - q * t); tie(u, v) = make_pair(v, u - q * v); } return make_tuple(s, u, a); } // floor(sqrt(N)) を求める (N < 0 のときは, 0 とする). ll isqrt(const ll &N) { if (N <= 0) { return 0; } ll x = sqrt(N); while ((x + 1) * (x + 1) <= N) { x++; } while (x * x > N) { x--; } return x; } // floor(sqrt(N)) を求める (N < 0 のときは, 0 とする). ll floor_sqrt(const ll &N) { return isqrt(N); } // ceil(sqrt(N)) を求める (N < 0 のときは, 0 とする). ll ceil_sqrt(const ll &N) { ll x = isqrt(N); return x * x == N ? x : x + 1; } #line 62 "/home/user/competitive_programming/library_for_cpp/template/template.hpp" // inout #line 1 "/home/user/competitive_programming/library_for_cpp/template/inout.hpp" // 入出力 template void input(T&... a){ (cin >> ... >> a); } void print(){ cout << "\n"; } template void print(const T& a, const Ts&... b){ cout << a; (cout << ... << (cout << " ", b)); cout << "\n"; } template istream &operator>>(istream &is, pair &P){ is >> P.first >> P.second; return is; } template ostream &operator<<(ostream &os, const pair &P){ os << P.first << " " << P.second; return os; } template vector vector_input(int N, int index){ vector X(N+index); for (int i=index; i> X[i]; return X; } template istream &operator>>(istream &is, vector &X){ for (auto &x: X) { is >> x; } return is; } template ostream &operator<<(ostream &os, const vector &X){ int s = (int)X.size(); for (int i = 0; i < s; i++) { os << (i ? " " : "") << X[i]; } return os; } template ostream &operator<<(ostream &os, const unordered_set &S){ int i = 0; for (T a: S) {os << (i ? " ": "") << a; i++;} return os; } template ostream &operator<<(ostream &os, const set &S){ int i = 0; for (T a: S) { os << (i ? " ": "") << a; i++; } return os; } template ostream &operator<<(ostream &os, const unordered_multiset &S){ int i = 0; for (T a: S) { os << (i ? " ": "") << a; i++; } return os; } template ostream &operator<<(ostream &os, const multiset &S){ int i = 0; for (T a: S) { os << (i ? " ": "") << a; i++; } return os; } #line 65 "/home/user/competitive_programming/library_for_cpp/template/template.hpp" // macro #line 2 "/home/user/competitive_programming/library_for_cpp/template/macro.hpp" // マクロの定義 #define all(x) x.begin(), x.end() #define len(x) ll(x.size()) #define elif else if #define unless(cond) if (!(cond)) #define until(cond) while (!(cond)) #define loop while (true) // オーバーロードマクロ #define overload2(_1, _2, name, ...) name #define overload3(_1, _2, _3, name, ...) name #define overload4(_1, _2, _3, _4, name, ...) name #define overload5(_1, _2, _3, _4, _5, name, ...) name // 繰り返し系 #define rep1(n) for (ll i = 0; i < n; i++) #define rep2(i, n) for (ll i = 0; i < n; i++) #define rep3(i, a, b) for (ll i = a; i < b; i++) #define rep4(i, a, b, c) for (ll i = a; i < b; i += c) #define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__) #define foreach1(x, a) for (auto &&x: a) #define foreach2(x, y, a) for (auto &&[x, y]: a) #define foreach3(x, y, z, a) for (auto &&[x, y, z]: a) #define foreach4(x, y, z, w, a) for (auto &&[x, y, z, w]: a) #define foreach(...) overload5(__VA_ARGS__, foreach4, foreach3, foreach2, foreach1)(__VA_ARGS__) #line 68 "/home/user/competitive_programming/library_for_cpp/template/template.hpp" // bitop #line 2 "/home/user/competitive_programming/library_for_cpp/template/bitop.hpp" // 非負整数 x の bit legnth を求める. ll bit_length(ll x) { if (x == 0) { return 0; } return (sizeof(long) * CHAR_BIT) - __builtin_clzll(x); } // 非負整数 x の popcount を求める. ll popcount(ll x) { return __builtin_popcountll(x); } // 正の整数 x に対して, floor(log2(x)) を求める. ll floor_log2(ll x) { return bit_length(x) - 1; } // 正の整数 x に対して, ceil(log2(x)) を求める. ll ceil_log2(ll x) { return bit_length(x - 1); } // x の第 k ビットを取得する int get_bit(ll x, int k) { return (x >> k) & 1; } // x のビット列を取得する. // k はビット列の長さとする. vector get_bits(ll x, int k) { vector bits(k); rep(i, k) { bits[i] = x & 1; x >>= 1; } return bits; } // x のビット列を取得する. vector get_bits(ll x) { return get_bits(x, bit_length(x)); } #line 2 "/home/user/competitive_programming/library_for_cpp/Geometry/utility/Convex_Hull.hpp" #line 2 "/home/user/competitive_programming/library_for_cpp/Geometry/utility/Counter_Clockwise.hpp" #line 2 "/home/user/competitive_programming/library_for_cpp/Geometry/object/Point.hpp" #line 2 "/home/user/competitive_programming/library_for_cpp/Geometry/base.hpp" #line 4 "/home/user/competitive_programming/library_for_cpp/Geometry/base.hpp" namespace geometry { using Real = double long; const Real epsilon = 1e-9; const Real pi = acos(static_cast(-1)); enum class Inclusion { OUT = -1, ON = 0, IN = 1 }; enum class Direction_Relation { PARALLEL = 1, ORTHOGONAL = -1, CROSS = 0}; inline int sign(const Real &r) { return r <= -epsilon ? -1 : r >= epsilon ? 1: 0; } inline int equal(const Real &a, const Real &b) { return sign(a - b) == 0; } inline int compare(const Real &a, const Real &b) { return sign(b - a); } inline int sign(const ll &r) { return r < 0 ? -1 : r > 0 ? 1 : 0; } inline int equal(const ll &a, const ll &b) { return sign(a - b) == 0; } inline int compare(const ll &a, const ll &b) { return sign(b - a); } inline int sign(const int &r) { return r < 0 ? -1 : r > 0 ? 1 : 0; } inline int equal(const int &a, const int &b) { return sign(a - b) == 0; } inline int compare(const int &a, const int &b) { return sign(b - a); } }; #line 4 "/home/user/competitive_programming/library_for_cpp/Geometry/object/Point.hpp" namespace geometry { template class Point { public: R x, y; public: Point(): x(0), y(0) {} Point(R _x, R _y): x(_x), y(_y) {} // 加法 Point& operator+=(const Point &B){ x += B.x; y += B.y; return *this; } friend Point operator+(const Point &P, const Point &Q) { return Point(P) += Q; } // 減法 Point& operator-=(const Point &B){ x -= B.x; y -= B.y; return *this; } friend Point operator-(const Point &P, const Point &Q) { return Point(P) -= Q; } // スカラー倍 Point& operator*=(const R &a){ x *= a; y *= a; return *this; } friend Point operator*(const Point &P, const R &a) { return Point(P) *= a; } friend Point operator*(const R &a, const Point &P) { return Point(P) *= a; } Point& operator/=(const R &a){ x /= a; y /= a; return *this; } friend Point operator/(const Point &P, const R &a) { return Point(P) /= a; } Point& operator*=(const Point &P){ R x1 = P.x * x - P.y * y, y1 = P.y * x + P.x * y; x = x1; y = y1; return *this; } friend Point operator*(const Point &P, const Point &Q) { return Point(P) *= Q; } friend istream& operator>>(istream &is, Point &P) { R a, b; is >> a >> b; P = Point(a, b); return is; } friend ostream& operator<<(ostream &os, const Point &P) { return os << P.x << " " << P.y; } inline R norm_2() const { return x * x + y * y; } inline double norm() const { return sqrt(norm_2()); } inline R dot(const Point B) const { return x * B.x + y * B.y; } inline R det(const Point B) const { return x * B.y - y * B.x; } inline Point normalize() const { return *this / norm(); } inline Point normal() const { return Point(-y, x); } inline Point rotate(double theta) const { Real alpha = sin(theta), beta = cos(theta); Real s = beta * x - alpha * y, t = alpha * x + beta * y; return Point(s, t); } }; template bool compare_x(const Point &A, const Point &B) { return equal(A.x, B.x) ? A.y < B.y : A.x < B.x; } template bool compare_y(const Point &A, const Point &B) { return equal(A.y, B.y) ? A.x < B.x : A.y < B.y; } template inline bool operator==(const Point &A, const Point &B) { return equal(A.x, B.x) && equal(A.y, B.y); } template inline bool operator!=(const Point &A, const Point &B) { return !(A == B); } template inline R dot(const Point &A, const Point &B) { return A.x * B.x + A.y * B.y; } template inline R cross(const Point &A, const Point &B) { return A.x * B.y - A.y * B.x; } template inline R norm_2(const Point &P) { return dot(P, P); } template inline double norm(const Point &P) { return sqrt(norm_2(P)); } template inline Real arg(const Point &P) { return atan2(P.y, P.x); } } #line 4 "/home/user/competitive_programming/library_for_cpp/Geometry/utility/Counter_Clockwise.hpp" namespace geometry { constexpr int COUNTER_CLOCKWISE = +1; constexpr int CLOCKWISE = -1; constexpr int ONLINE_BACK = -2; // c-a-b constexpr int ONLINE_FRONT = +2; // a-b-c constexpr int ON_SEGMENT = 0; // a-c-b // A -> B -> C と進んだ時の進行方向を調べる (B 視点) // Input // A: 始点 // B: 中継地点 // C: 終点 template int Counter_Clockwise(const Point &A, Point B, Point C) { B = B - A; C = C - A; if (sign(cross(B, C)) == +1) { return COUNTER_CLOCKWISE; } if (sign(cross(B, C)) == -1) { return CLOCKWISE; } if (sign(dot(B, C)) == -1) { return ONLINE_BACK; } if (norm_2(B) < norm_2(C)) { return ONLINE_FRONT; } return ON_SEGMENT; } } #line 2 "/home/user/competitive_programming/library_for_cpp/Geometry/object/Polygon.hpp" #line 4 "/home/user/competitive_programming/library_for_cpp/Geometry/object/Polygon.hpp" namespace geometry { template struct Polygon { vector> vertices; int n; Polygon() = default; Polygon(const vector> &_vertices): vertices(_vertices), n(_vertices.size()) {} }; template R Area(const Polygon &X) { R area = cross(X.vertices[X.n - 1], X.vertices[0]); for (int i = 0; i < X.n - 1; i++) { area += cross(X.vertices[i], X.vertices[i + 1]); } return abs(area) / 2; } } #line 5 "/home/user/competitive_programming/library_for_cpp/Geometry/utility/Convex_Hull.hpp" namespace geometry { template Polygon Convex_Hull(vector> points, bool strict = true) { // 前処理 sort(points.begin(), points.end(), compare_x); points.erase(unique(points.begin(), points.end()), points.end()); int n = points.size(); if (n <= 2) { return Polygon(points); } int k = 0; vector> vertices(2 * n); auto is_valid = [&](const int i) -> bool { int d = Counter_Clockwise(vertices[k - 2], vertices[k - 1], points[i]); return (d == COUNTER_CLOCKWISE || (!strict && d == ONLINE_FRONT)); }; for (int i = 0; i < n; vertices[k++] = points[i++]) { if (!vertices.empty() && vertices.back() == points[i]) { vertices.pop_back(); } while(k >= 2 && !is_valid(i)) { k--; } } for (int i = n - 2, t = k + 1; i >= 0; vertices[k++] = points[i--]) { if (!vertices.empty() && vertices.back() == points[i]) { vertices.pop_back(); } while (k >= t && !is_valid(i)) { k--; } } vertices.resize(k - 1); return Polygon(vertices); } } #line 3 "program.cpp" using namespace geometry; namespace geometry { bool operator<(const Point &P, const Point &Q) { return compare_x(P, Q); } }; void solve() { int N; cin >> N; vector> P(N); for (int i = 0; i < N; i++) { cin >> P[i]; } Polygon C = Convex_Hull(P, true); int m = C.n; map, int> dict; for (int i = 0; i < N; i++) { dict[P[i]] = i; } vector> ans(N, {0, 0}); if (m == 2) { Point S = C.vertices[0], T = C.vertices[1]; int i = dict[S], j = dict[T]; // (a, b) = (±1, 0), (0, ±1) を調べれば十分. vector> candidates{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; for (auto &[a, b]: candidates) { if (a * S.x + b * S.y > a * T.x + b * T.y) { ans[i] = {a, b}; ans[j] = {-a, -b}; } } } else { for (int j = 0; j < m; j++) { int i = dict[C.vertices[j]]; Point v = C.vertices[mod(j + 1, m)] - C.vertices[mod(j - 1, m)]; ans[i] = { v.y, -v.x }; } } for (auto &[a, b]: ans) { if (a == 0 && b == 0) { cout << "No" << "\n"; } else { cout << a << " " << b << "\n"; } } } int main() { int T; cin >> T; for (int t = 1; t <= T; t++) { solve(); } }