src/math/frac.hpp

• View this file on GitHub
• Last update: 2020-05-22 19:22:07+09:00
• Include: #include "src/math/frac.hpp"

Depends on

• src/bitop.hpp
• src/math/primitive.hpp

Code

#pragma once

#include "math/primitive.hpp"


template <class I> struct Frac {
    I a, b;  // a / b
    Frac(I _a = 0) : a(_a), b(1) {}
    Frac(I _a, I _b) {
        I g = gcd(_a, _b);
        if (_b < 0) g = -g;
        a = _a / g;
        b = _b / g;
    }
    Frac operator-() const {
        Frac f;
        f.a = -a;
        f.b = b;
        return f;
    }
    Frac operator+(const Frac& r) const { return {r.b * a + b * r.a, b * r.b}; }
    Frac operator-(const Frac& r) const { return *this + (-r); }
    Frac operator*(const Frac& r) const { return {a * r.a, b * r.b}; }
    Frac operator/(const Frac& r) const { return {a * r.b, b * r.a}; }
    Frac& operator+=(const Frac& r) { return *this = *this + r; }
    Frac& operator-=(const Frac& r) { return *this = *this - r; }
    Frac& operator*=(const Frac& r) { return *this = *this * r; }
    Frac& operator/=(const Frac& r) { return *this = *this / r; }
    bool operator<(const Frac& r) const { return a * r.b < b * r.a; }
    bool operator>(const Frac& r) const { return r < *this; }
    bool operator<=(const Frac& r) const { return !(r < *this); }
    bool operator>=(const Frac& r) const { return !(*this < r); }
    bool operator==(const Frac& r) const {
        return !(*this < r) && !(r < *this);
    }
    bool operator!=(const Frac& r) const { return !(*this == r); }

    static Frac rec(Frac x, Frac y, Frac l, Frac r) {
        auto flip = [&](Frac& f) { f = Frac(1) - f; };
        auto cross = [&](const Frac& f, const Frac& g) {
            return f.a * g.b - f.b * g.a;
        };
        Frac m = {l.a + r.a, l.b + r.b};
        if (x < m && m < y) return m;
        bool s = !(x < m);
        if (s) {
            flip(l);
            flip(r);
            flip(m);
            flip(x);
            flip(y);
            swap(l, r);
            swap(x, y);
        }
        I k = cross(r, y) / cross(y, l) + 1;
        Frac p = {k * l.a + r.a, k * l.b + r.b};
        if (x < p) {
            if (s) flip(p);
            return p;
        }
        Frac q = rec(x, y, p, {(k - 1) * l.a + r.a, (k - 1) * l.b + r.b});
        if (s) flip(q);
        return q;
    }
    static Frac in_bet(Frac x, Frac y) {
        if (y < x) swap(x, y);
        Frac ret;
        I num = x.a >= 0 ? x.a / x.b : -((x.b - 1 - x.a) / x.b);
        x.a -= x.b * num;
        y.a -= y.b * num;
        if (Frac{1, 1} < y)
            ret = Frac{1, 1};
        else
            ret = rec(x, y, Frac{0, 1}, Frac{1, 1});
        ret.a += ret.b * num;
        return ret;
    }
};

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.10.1/x64/lib/python3.10/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
  File "/opt/hostedtoolcache/Python/3.10.1/x64/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.10.1/x64/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
  File "/opt/hostedtoolcache/Python/3.10.1/x64/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: math/primitive.hpp: line -1: no such header

Back to top page