結果

問題 No.3437 [Cherry 8th Tune C] Silhouette
コンテスト
ユーザー Moss_Local
提出日時 2026-01-31 18:27:44
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 3,015 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,599 ms
コンパイル使用メモリ 170,596 KB
実行使用メモリ 7,972 KB
最終ジャッジ日時 2026-01-31 18:27:53
合計ジャッジ時間 8,401 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

using namespace std;

long long MOD = 998244353;

// モジュラ演算用構造体 (簡易版)
struct mint {
    long long x;
    mint(long long x = 0) : x((x % MOD + MOD) % MOD) {}
    mint operator-() const { return mint(-x); }
    mint& operator+=(const mint a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += MOD - a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint operator+(const mint a) const { return mint(*this) += a; }
    mint operator-(const mint a) const { return mint(*this) -= a; }
    mint operator*(const mint a) const { return mint(*this) *= a; }
    
    // 累乗 (逆元計算に使用)
    mint pow(long long t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // 逆元 (Fermat's Little Theorem)
    mint inv() const { return pow(MOD - 2); }
    mint& operator/=(const mint a) { return *this *= a.inv(); }
    mint operator/(const mint a) const { return mint(*this) /= a; }
};

// 座標を表す構造体
struct Point {
    long long x, y, z;
};

// 2次元座標 (modint版)
struct Point2D {
    mint x, y;
};

void solve() {
    Point A, B, C, L;
    cin >> A.x >> A.y >> A.z;
    cin >> B.x >> B.y >> B.z;
    cin >> C.x >> C.y >> C.z;
    cin >> L.x >> L.y >> L.z;

    // 3点 A, B, C を xy平面に射影する関数
    // 点 P の射影 P' = L + (lz / (lz - pz)) * (P - L)
    auto project = [&](Point P) -> Point2D {
        // 分母: lz - pz (制約より必ず正だが、mod計算のため0になることはない)
        mint den = mint(L.z) - mint(P.z);
        // 係数 k = lz / (lz - pz)
        mint k = mint(L.z) / den;

        mint px = mint(L.x) + k * (mint(P.x) - mint(L.x));
        mint py = mint(L.y) + k * (mint(P.y) - mint(L.y));
        return {px, py};
    };

    Point2D A_prime = project(A);
    Point2D B_prime = project(B);
    Point2D C_prime = project(C);

    // 面積計算: クロス積の 1/2
    // S = 0.5 * | (Bx - Ax)(Cy - Ay) - (Cx - Ax)(By - Ay) |
    mint vecAB_x = B_prime.x - A_prime.x;
    mint vecAB_y = B_prime.y - A_prime.y;
    mint vecAC_x = C_prime.x - A_prime.x;
    mint vecAC_y = C_prime.y - A_prime.y;

    mint cross_product = vecAB_x * vecAC_y - vecAC_x * vecAB_y;
    
    // 面積 S = cross_product / 2
    // ここで符号が負になる場合(mod上で大きな値になる場合)も、
    // 問題の定義的にそのまま 2 で割ればよい。
    // (通常、modの世界での面積問題は符号を気にせず計算結果を出力する)
    mint ans = cross_product / 2;

    cout << ans.x << "\n";
}

int main() {
    // 高速化
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}
0