/** * 問題: N個の点それぞれについて、その点での値が他より真に大きくなる係数(A, B)を求める * 修正点: ベクトル(A, B)の向きを反転し、凸包の外側(最大化する方向)に向くように修正。 */ #include #include #include using namespace std; // 座標を扱う構造体 struct Point { long long x, y; int id; // 元のインデックス(0-indexed) // ソート用: x優先、次にy bool operator<(const Point& other) const { if (x != other.x) return x < other.x; return y < other.y; } // ベクトル減算 Point operator-(const Point& other) const { return {x - other.x, y - other.y, -1}; } }; // ベクトル外積 (2D) // CP > 0: 反時計回り (左折) // CP = 0: 直線 // CP < 0: 時計回り (右折) long long cross_product(Point a, Point b, Point c) { return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); } struct Answer { bool possible; long long A, B; }; void solve() { int N; cin >> N; vector P(N); for (int i = 0; i < N; ++i) { cin >> P[i].x >> P[i].y; P[i].id = i; } // 凸包構築 (Monotone Chain) sort(P.begin(), P.end()); vector hull; // 下側凸包 // cross_product <= 0 (一直線上の点を含む) は削除対象とし、 // 厳密な凸頂点(strictly convex vertex)のみを残す for (int i = 0; i < N; ++i) { while (hull.size() >= 2 && cross_product(hull[hull.size() - 2], hull.back(), P[i]) <= 0) { hull.pop_back(); } hull.push_back(P[i]); } // 上側凸包 int lower_size = hull.size(); for (int i = N - 2; i >= 0; --i) { while (hull.size() > lower_size && cross_product(hull[hull.size() - 2], hull.back(), P[i]) <= 0) { hull.pop_back(); } hull.push_back(P[i]); } // 始点が重複するので削除(サイズ>1の場合) if (hull.size() > 1) hull.pop_back(); // 結果格納用 vector ans(N, {false, 0, 0}); // 凸包上の点に対して答えを計算 int K = hull.size(); for (int i = 0; i < K; ++i) { int original_id = hull[i].id; ans[original_id].possible = true; if (K == 2) { // 凸包が2点だけの場合(全ての点が一直線上にある場合の両端など) // 相手側から自分に向かうベクトルを使えば自分が最大になる Point target = hull[i]; Point other = hull[(i + 1) % K]; // (A, B) = 自分 - 相手 ans[original_id].A = target.x - other.x; ans[original_id].B = target.y - other.y; } else { // 通常の凸包 // 順序は反時計回り(CCW)になっている Point prev = hull[(i + K - 1) % K]; Point next = hull[(i + 1) % K]; // 弦(prev -> next)を考える。 // 凸包がCCWなので、現在の点(target)は、ベクトル(prev->next)の進行方向に対して「右側」にある。 // (A, B) はこの弦の法線ベクトルであり、かつ target のある右側(外側)を向く必要がある。 // ベクトル V = (dx, dy) = (next.x - prev.x, next.y - prev.y) // 右向き法線(時計回り90度回転)は (dy, -dx) long long A = next.y - prev.y; // dy long long B = -(next.x - prev.x); // -dx = prev.x - next.x ans[original_id].A = A; ans[original_id].B = B; } } // 出力 for (int i = 0; i < N; ++i) { if (ans[i].possible) { cout << ans[i].A << " " << ans[i].B << "\n"; } else { cout << "No\n"; } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T--) { solve(); } return 0; }