結果

問題 No.2628 Shrinkage
ユーザー Today03Today03
提出日時 2024-02-16 22:41:04
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 5,343 bytes
コンパイル時間 2,298 ms
コンパイル使用メモリ 206,248 KB
実行使用メモリ 6,676 KB
最終ジャッジ日時 2024-02-16 22:41:30
合計ジャッジ時間 3,454 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,548 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#ifdef LOCAL
#include "./debug.cpp"
#else
#define debug(...)
#define print_line
#endif
using namespace std;
using ll = long long;

#include <iostream>

/**
 * @brief Modint
 */

template <long long MOD>
struct modint {
    long long value;
    modint(long long x = 0) {
        if (x >= 0) {
            value = x % MOD;
        } else {
            value = MOD - (-x) % MOD;
        }
    }
    modint operator-() const {
        return modint(-value);
    }
    modint operator+() const {
        return modint(*this);
    }
    modint &operator+=(const modint &other) {
        value += other.value;
        if (value >= MOD) {
            value -= MOD;
        }
        return *this;
    }
    modint &operator-=(const modint &other) {
        value += MOD - other.value;
        if (value >= MOD) {
            value -= MOD;
        }
        return *this;
    }
    modint &operator*=(const modint other) {
        value = value * other.value % MOD;
        return *this;
    }
    modint &operator/=(modint other) {
        (*this) *= other.inv();
        return *this;
    }
    modint operator+(const modint &other) const {
        return modint(*this) += other;
    }
    modint operator-(const modint &other) const {
        return modint(*this) -= other;
    }
    modint operator*(const modint &other) const {
        return modint(*this) *= other;
    }
    modint operator/(const modint &other) const {
        return modint(*this) /= other;
    }
    modint pow(long long x) const {
        modint ret(1), mul(value);
        while (x > 0) {
            if (x % 2 == 1) {
                ret *= mul;
            }
            mul *= mul;
            x /= 2;
        }
        return ret;
    }
    modint inv() const {
        return pow(MOD - 2);
    }
    bool operator==(const modint &other) const {
        return value == other.value;
    }
    bool operator!=(const modint &other) const {
        return value != other.value;
    }
    friend std::ostream &operator<<(std::ostream &os, const modint &x) {
        return os << x.value;
    }
    friend std::istream &operator>>(std::istream &is, modint &x) {
        long long v;
        is >> v;
        x = modint<MOD>(v);
        return is;
    }
};
using mod998 = modint<998244353>;
using mod107 = modint<1000000007>;

using Real = mod998;
;
bool equals(Real a, Real b) { return a == b; }

template <typename R>
struct PointBase {
    using P = PointBase;
    R x, y;
    PointBase() : x(0), y(0) {}
    PointBase(R _x, R _y) : x(_x), y(_y) {}
    template <typename T, typename U>
    PointBase(const pair<T, U> &p) : x(p.first), y(p.second) {}

    P operator+(const P &r) const { return {x + r.x, y + r.y}; }
    P operator-(const P &r) const { return {x - r.x, y - r.y}; }
    P operator*(R r) const { return {x * r, y * r}; }
    P operator/(R r) const { return {x / r, y / r}; }

    P &operator+=(const P &r) { return (*this) = (*this) + r; }
    P &operator-=(const P &r) { return (*this) = (*this) - r; }
    P &operator*=(R r) { return (*this) = (*this) * r; }
    P &operator/=(R r) { return (*this) = (*this) / r; }

    bool operator==(const P &r) const { return x == r.x and y == r.y; }
    bool operator!=(const P &r) const { return !((*this) == r); }

    R real() const { return x; }
    R imag() const { return y; }
    friend R real(const P &p) { return p.x; }
    friend R imag(const P &p) { return p.y; }
    friend R dot(const P &l, const P &r) { return l.x * r.x + l.y * r.y; }
    friend R cross(const P &l, const P &r) { return l.x * r.y - l.y * r.x; }
    friend R mynorm(const P &p) { return p.x * p.x + p.y * p.y; }
};
using Point = PointBase<Real>;
using Points = vector<Point>;

struct Line {
    Point a, b;

    Line() = default;
    Line(const Point &_a, const Point &_b) : a(_a), b(_b) {}
    // Ax+By=C
    Line(const Real &A, const Real &B, const Real &C) {
        if (equals(A, 0)) {
            assert(!equals(B, 0));
            a = Point(0, C / B);
            b = Point(1, C / B);
        } else if (equals(B, 0)) {
            a = Point(C / A, 0);
            b = Point(C / A, 1);
        } else if (equals(C, 0)) {
            a = Point(0, C / B);
            b = Point(1, (C - A) / B);
        } else {
            a = Point(0, C / B);
            b = Point(C / A, 0);
        }
    }
};
using Lines = vector<Line>;

Point cross_point_ll(const Line &l, const Line &m) {
    Real A = cross(l.b - l.a, m.b - m.a);
    Real B = cross(l.b - l.a, l.b - m.a);
    if (equals(A, 0) && equals(B, 0)) return m.a;
    return m.a + (m.b - m.a) * B / A;
}

bool is_parallel(const Line &a, const Line &b) {
    return equals(cross(a.b - a.a, b.b - b.a), 0);
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        vector<Point> P(4);
        for (int i = 0; i < 4; i++) {
            long long x, y;
            cin >> x >> y;
            P[i].x = x;
            P[i].y = y;
        }

        Line la(P[0], P[2]), lb(P[1], P[3]);

        if (is_parallel(la, lb)) {
            cout << "No" << endl;
            continue;
        }
        Point crs = cross_point_ll(la, lb);

        Real d1 = mynorm(P[0] - P[2]), d2 = mynorm(P[1] - P[3]);
        Real d3 = mynorm(P[0] - crs), d4 = mynorm(P[1] - crs);
        debug(d1, d2);

        cout << (d1 * d4 == d3 * d2 ? "Yes" : "No") << endl;
    }
}
0