結果

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

ソースコード

diff #
raw source code 

/**
 * 問題: N個の点それぞれについて、その点での値が他より真に大きくなる係数(A, B)を求める
 * 修正点: ベクトル(A, B)の向きを反転し、凸包の外側（最大化する方向）に向くように修正。
 */

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

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