/** * 問題: N個の点それぞれについて、その点での値が他より真に大きくなる係数(A, B)を求める * 解法: 凸包の厳密な頂点(strictly convex vertex)のみが Yes。 * (A, B)は隣接頂点を結ぶ弦の法線ベクトルとして構築可能。 */ #include #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; } // 等価判定 bool operator==(const Point& other) const { return x == other.x && y == other.y; } }; // ベクトル外積 (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; } // Nが非常に小さい場合のコーナーケース // 制約により入力の点は全て異なるが、N=1の場合は自明に条件を満たす(他が存在しないため) // ただし問題文の条件「j != i である任意の整数 j について...」 // N=1の場合、条件式自体が空集合に対する条件なので真(Vacuously true)。適当な値を出力。 // しかし制約で N >= 2 とあるので考慮不要。 // 凸包構築 (Monotone Chain) // ソート sort(P.begin(), P.end()); // 凸包の頂点を格納するリスト // strictly convexな頂点のみを残すため、cross_product <= 0 でpopする vector hull; // 下側凸包 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) { // 元のIDを取得 int original_id = hull[i].id; ans[original_id].possible = true; if (K == 2) { // 凸包が潰れている(全点が同一直線上にある)場合 // 両端のみがHullに含まれる。 // 相手側への方向ベクトルを採用 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 { // 通常の凸包 Point prev = hull[(i + K - 1) % K]; Point next = hull[(i + 1) % K]; // 弦(prev -> next)の法線ベクトルを計算 // ベクトル V = next - prev // Vを時計回りに90度回転させたものが外向き法線 (ただしY軸反転等に注意) // 単純に数式で導出: A(x_next - x_prev) + B(y_next - y_prev) = 0 // 解の一つ: A = y_prev - y_next, B = x_next - x_prev long long A = prev.y - next.y; long long B = next.x - prev.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; }