結果

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

ソースコード

diff #
raw source code 

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

#include <atcoder/all>
#define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
using namespace atcoder;
using namespace std;

typedef long long ll;

using mint = modint998244353;

struct Fraction {
    /**
     * p / q
     * https://atcoder.jp/contests/abc390/submissions/72321330
     */
    mint p, q;
    Fraction(ll P = 0, ll Q = 1) : p(P), q(Q) {}
    Fraction(mint P, mint Q) : p(P), q(Q) {}

    Fraction operator+(const Fraction &other) const {
        return Fraction(p * other.q + q * other.p, q * other.q);
    }
    Fraction operator-(const Fraction &other) const {
        return Fraction(p * other.q - q * other.p, q * other.q);
    }
    Fraction operator*(const Fraction &other) const {
        return Fraction(p * other.p, q * other.q);
    }
    Fraction operator/(const Fraction &other) const {
        return Fraction(p * other.q, q * other.p);
    }
};

pair<Fraction, Fraction> f(tuple<ll, ll, ll> a, tuple<ll, ll, ll> b) {
    auto [ax, ay, az] = a;
    auto [bx, by, bz] = b;
    Fraction kake(az, az - bz);
    auto dx = ax - bx;
    auto dy = ay - by;
    auto dz = az - bz;
    pair<Fraction, Fraction> ret = {(Fraction)ax + (Fraction)dx * kake,
                                    (Fraction)ay + (Fraction)dy * kake};
    return ret;
}

void input(tuple<ll, ll, ll> &A) {
    ll x, y, z;
    cin >> x >> y >> z;
    A = {x, y, z};
}

mint g(pair<Fraction, Fraction> a, pair<Fraction, Fraction> b,
       pair<Fraction, Fraction> c) {
    auto [ax, ay] = a;
    auto [bx, by] = b;
    auto [cx, cy] = c;
    Fraction adx = ax - cx, ady = ay - cy;
    Fraction bdx = bx - cx, bdy = by - cy;
    Fraction t = adx * bdy - ady * bdx;
    mint ret = t.p / t.q / 2;
    return ret;
}

ll h(tuple<ll, ll, ll> A, tuple<ll, ll, ll> B, tuple<ll, ll, ll> C,
     tuple<ll, ll, ll> P) {
    auto [ax, ay, az] = A;
    auto [bx, by, bz] = B;
    auto [cx, cy, cz] = C;
    auto [px, py, pz] = P;
    ll axp = ax - px, ayp = ay - py, azp = az - pz;
    ll bxp = bx - px, byp = by - py, bzp = bz - pz;
    ll cxp = cx - px, cyp = cy - py, czp = cz - pz;
    ll x = ayp * bzp - azp * byp;
    ll y = azp * bxp - axp * bzp;
    ll z = axp * byp - ayp * bxp;
    return x * cxp + y * cyp + z * czp;
}

void solve() {
    tuple<ll, ll, ll> A, B, C, P;
    input(A);
    input(B);
    input(C);
    input(P);
    if (h(A, B, C, P) > 0) {
        swap(B, C);
    }
    auto p = f(P, A);
    auto q = f(P, B);
    auto r = f(P, C);
    mint ans = g(p, q, r);
    cout << ans.val() << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    int t;
    cin >> t;
    while (t--) solve();
}
0