結果

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

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>

using namespace std;

long long power(long long base, long long exp) {
    long long res = 1;
    base %= 998244353;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % 998244353;
        base = (base * base) % 998244353;
        exp /= 2;
    }
    return res;
}

long long modInverse(long long n) {
    return power(n, 998244353 - 2);
}

void solve() {
    long long ax, ay, az, bx, by, bz, cx, cy, cz, lx, ly, lz;
    cin >> ax >> ay >> az >> bx >> by >> bz >> cx >> cy >> cz >> lx >> ly >> lz;

    auto get_projected = [&](long long px, long long py, long long pz) {
        // t = lz / (lz - pz)
        // x' = lx + t * (px - lx) = (lx(lz - pz) + lz(px - lx)) / (lz - pz)
        // 分子を整理すると: (lx*lz - lx*pz + lz*px - lz*lx) / (lz - pz) = (lz*px - lx*pz) / (lz - pz)
        long long num_x = (lz % 998244353 * (px % 998244353 + 998244353) % 998244353 
                          - lx % 998244353 * (pz % 998244353 + 998244353) % 998244353 + 998244353) % 998244353;
        long long num_y = (lz % 998244353 * (py % 998244353 + 998244353) % 998244353 
                          - ly % 998244353 * (pz % 998244353 + 998244353) % 998244353 + 998244353) % 998244353;
        long long den = (lz - pz + 998244353) % 998244353;
        
        long long inv_den = modInverse(den);
        return make_pair(num_x * inv_den % 998244353, num_y * inv_den % 998244353);
    };

    // xy平面への投影点 A', B', C' を求める
    auto [x1, y1] = get_projected(ax, ay, az);
    auto [x2, y2] = get_projected(bx, by, bz);
    auto [x3, y3] = get_projected(cx, cy, cz);

    // 面積 S = 1/2 * |(x1-x3)(y2-y3) - (x2-x3)(y1-y3)|
    long long term1 = (x1 - x3 + 998244353) % 998244353 * (y2 - y3 + 998244353) % 998244353;
    long long term2 = (x2 - x3 + 998244353) % 998244353 * (y1 - y3 + 998244353) % 998244353;
    long long s = (term1 - term2 + 998244353) % 998244353;
    
    // 2で割る（逆元をかける）。絶対値は不要（注記の定義より、外積が負でもmod上では正当な値になる）
    // もし S=0 ならそのまま 0 になる
    s = s * modInverse(2) % 998244353;

    cout << s << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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