結果

問題 No.3005 トレミーの問題
ユーザー Tatsu_mr
提出日時 2025-01-17 22:45:23
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 5,454 bytes
コンパイル時間 3,611 ms
コンパイル使用メモリ 283,560 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2025-01-17 22:45:32
合計ジャッジ時間 4,648 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#define For(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, n) For(i, 0, n)
#define rFor(i, a, b) for(int i = (a); i >= (b); i--)
#define ALL(v) (v).begin(), (v).end()
#define rALL(v) (v).rbegin(), (v).rend()
using lint = long long;
using ld = long double;
int INF = 2000000000;
lint LINF = 1000000000000000000;
struct Fraction {
    using lint = long long;
    
    private:
    lint gcd(lint a_, lint b_) {
        unsigned long long a = abs(a_), b = abs(b_);
        if (a == 0 || b == 0) {
            return (a == 0 ? b : a);
        }
        int x = __builtin_ctzll(a), y = __builtin_ctzll(b);
        a >>= x;
        b >>= y;
        while (a != b) {
            if (a < b) {
                swap(a, b);
            }
            a -= b;
            a >>= __builtin_ctzll(a);
        }
        return (a << min(x, y));
    }
    
    void reduce() {
        if (p != 0) {
            lint g = gcd(abs(p), abs(q));
            p /= g;
            q /= g;
        } else {
            q = 1;
        }
    }
    
    int comp(lint a, lint b, lint c, lint d) const {
        if (a == c && b == d) {
            return 0;
        }
        return (a * d < c * b ? -1 : 1);
    }
    public:
    lint p, q;
    
    Fraction() : p(0), q(1) {}
    Fraction(lint p_, lint q_) : p(p_), q(q_) {
        assert(q_ != 0);
        if (q < 0) {
            p = -p;
            q = -q;
        }
        reduce();
    }
    Fraction(lint p_) : p(p_), q(1) {}
    
    Fraction &operator+=(const Fraction &a) {
        lint np = p * a.q + q * a.p;
        lint nq = q * a.q;
        *this = Fraction(np, nq);
        return *this;
    }
    
    Fraction &operator-=(const Fraction &a) {
        lint np = p * a.q - q * a.p;
        lint nq = q * a.q;
        *this = Fraction(np, nq);
        return *this;
    }
    
    Fraction &operator*=(const Fraction &a) {
        lint np = p * a.p;
        lint nq = q * a.q;
        *this = Fraction(np, nq);
        return *this;
    }
    
    Fraction &operator/=(const Fraction &a) {
        assert(a.p != 0);
        lint np = p * a.q;
        lint nq = q * a.p;
        *this = Fraction(np, nq);
        return *this;
    }
    
    Fraction operator+(const Fraction &a) {
        return Fraction(*this) += a;
    }
    
    Fraction operator-(const Fraction &a) {
        return Fraction(*this) -= a;
    }
    
    Fraction operator*(const Fraction &a) {
        return Fraction(*this) *= a;
    }
    
    Fraction operator/(const Fraction &a) {
        return Fraction(*this) /= a;
    }
    
    Fraction operator-() {
        p = -p;
        return *this;
    }
    
    bool operator==(const Fraction &a) const {
        return comp(p, q, a.p, a.q) == 0;
    }
    
    bool operator!=(const Fraction &a) const {
        return comp(p, q, a.p, a.q) != 0;
    }
    
    bool operator<(const Fraction &a) const {
        return comp(p, q, a.p, a.q) == -1;
    }
    
    bool operator>(const Fraction &a) const {
        return comp(p, q, a.p, a.q) == 1;
    }
    
    bool operator<=(const Fraction &a) const {
        return comp(p, q, a.p, a.q) <= 0;
    }
    
    bool operator>=(const Fraction &a) const {
        return comp(p, q, a.p, a.q) >= 0;
    }
    
    friend ostream &operator<<(ostream &os, Fraction a) {
        return os << a.p << "/" << a.q;
    }
};
using F = Fraction;
using Point = pair<lint, lint>;
using Line = pair<F, F>;
Line get_line(Point p, Point q) {
    auto [x1, y1] = p;
    auto [x2, y2] = q;
    if (x1 != x2) {
        F A = F((y1 - y2), (x1 - x2));
        F B = F((y2 - y1), (x1 - x2)) * F(x1) + F(y1);
        return {A, B};
    } else {
        return {F(x1), F(LINF)};
    }
}
bool same_side(Point p, Point q, Line l) {
    auto [x1, y1] = p;
    auto [x2, y2] = q;
    auto [a, b] = l;
    if (b != F(LINF)) {
        F Y1 = a * F(x1) + b;
        F Y2 = a * F(x2) + b;
        if (Y1 > y1 && Y2 > y2) {
            return true;
        }
        if (Y1 < y1 && Y2 < y2) {
            return true;
        }
        return false;
    } else {
        lint x = a.p;
        if (x1 < x && x2 < x) {
            return true;
        }
        if (x1 > x && x2 > x) {
            return true;
        }
        return false;
    }
}
ld get_angle(Point p, Point q, Point r) {
    auto [x1, y1] = p;
    auto [x2, y2] = q;
    auto [x3, y3] = r;
    using Vector = pair<F, F>;
    Vector pq = {F(x2 - x1), F(y2 - y1)};
    Vector pr = {F(x3 - x1), F(y3 - y1)};
    F ipf = pq.first * pr.first + pq.second * pr.second;
    F len_pq2 = pq.first * pq.first + pq.second * pq.second;
    F len_pr2 = pr.first * pr.first + pr.second * pr.second;
    ld ip = ld(ipf.p) / ld(ipf.q);
    ld len_pq = sqrt(ld(len_pq2.p) / ld(len_pq2.q));
    ld len_pr = sqrt(ld(len_pr2.p) / ld(len_pr2.q));
    ld cosine = ip / len_pq / len_pr;
    return acos(cosine);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<Point> ps(4);
    rep(i, 4) {
        cin >> ps[i].first >> ps[i].second;
    }
    vector<int> ind = {0, 1, 2, 3};
    do {
        Point p = ps[ind[0]], q = ps[ind[1]], r = ps[ind[2]], s = ps[ind[3]];
        Line l = get_line(r, s);
        if (same_side(p, q, l)) {
            if (get_angle(p, r, s) == get_angle(q, r, s)) {
                cout << "YES\n";
                return 0;
            }
        }
    } while (next_permutation(ALL(ind)));
    cout << "NO\n";
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0