結果

問題 No.3438 [Cherry 8th Tune D] 競プロは向いてない
コンテスト
ユーザー Moss_Local
提出日時 2026-01-31 18:40:25
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 4,426 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,231 ms
コンパイル使用メモリ 183,628 KB
実行使用メモリ 12,816 KB
最終ジャッジ日時 2026-01-31 18:41:11
合計ジャッジ時間 42,916 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other AC * 3 WA * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/**
 * 問題: N個の点それぞれについて、その点での値が他より真に大きくなる係数(A, B)を求める
 * 解法: 凸包の厳密な頂点(strictly convex vertex)のみが Yes。
 * (A, B)は隣接頂点を結ぶ弦の法線ベクトルとして構築可能。
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

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<Point> 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<Point> 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<Answer> 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;
}
0