library/linearalgebra/Linear.hpp

• View this file on GitHub
• Last update: 2025-11-24 18:49:07+09:00
• Include: #include "library/linearalgebra/Linear.hpp"
• Link: View error logs on GitHub Actions

Depends on

• build/pch/stdc++.hpp

Required by

• library/algebra/group/Affine.hpp
• library/algebra/lazy/AffineSum.hpp
• library/linearalgebra/ConvexHullTrick.hpp
• library/linearalgebra/InsertConvexHullTrick.hpp

Verified with

• test/library-checker/DataStructure/PointSetRangeComposite.test.cpp
• test/library-checker/DataStructure/QueueOperateAllComposite.test.cpp
• test/library-checker/DataStructure/RangeAffineRangeSum.test.cpp
• test/library-checker/Tree/vertex_set_path_composite.test.cpp
• test/yukicoder/2012.test.cpp

Code

#pragma once
template <typename T> struct Line {
    T a, b;
    Line() = default;
    Line(T a, T b) : a(a), b(b) {}
    Line(std::pair<T, T> l) : a(l.first), b(l.second) {}
    Line(T c) : a(0), b(c) {}

    T operator()(const T x) const { return a * x + b; }
    Line operator()(const Line &l) const { return Line(a * l.a, a * l.b + b); }

    bool operator==(const Line &l) const { return a == l.a and b == l.b; }
    bool operator!=(const Line &l) const { return !(*this == l); }
    bool operator<(const Line &l) const {
        return (a == l.a ? a < l.a : b < l.b);
    }

    Line &operator+=(const Line &l) {
        a += l.a;
        b += l.b;
        return *this;
    }
    Line operator+(const Line &l) const { return Line(*this) += l; }
    Line &operator-=(const Line &l) {
        a -= l.a;
        b -= l.b;
        return *this;
    }
    Line operator-(const Line &l) const { return Line(*this) -= l; }
    Line operator-() const { return Line(-a, -b); }

    Line &operator+=(const T &c) {
        b += c;
        return *this;
    }
    Line operator+(const T &c) const { return Line(*this) += c; }
    Line &operator-=(const T &c) {
        b -= c;
        return *this;
    }
    Line operator-(const T &c) const { return Line(*this) -= c; }
    Line &operator*=(const T &c) {
        a *= c;
        b *= c;
        return *this;
    }
    Line operator*(const T &c) const { return Line(*this) *= c; }
    Line &operator/=(const T &c) {
        a /= c;
        b /= c;
        return *this;
    }
    Line operator/(const T &c) const { return Line(*this) /= c; }

    Line inv() const {
        assert(a != 0);
        return Line(T(1) / a, -b / a);
    }

    friend std::istream &operator>>(std::istream &is, Line &l) {
        is >> l.a >> l.b;
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Line &l) {
        if (l.a == 0 and l.b == 0)
            os << 0;
        else if (l.a == 0)
            os << l.b;
        else if (l.b == 0)
            os << l.a << "x";
        else if (l.b > 0)
            os << l.a << "x+" << l.b;
        else
            os << l.a << "x-" << -l.b;
        return os;
    }
};

#line 2 "library/linearalgebra/Linear.hpp"
template <typename T> struct Line {
    T a, b;
    Line() = default;
    Line(T a, T b) : a(a), b(b) {}
    Line(std::pair<T, T> l) : a(l.first), b(l.second) {}
    Line(T c) : a(0), b(c) {}

    T operator()(const T x) const { return a * x + b; }
    Line operator()(const Line &l) const { return Line(a * l.a, a * l.b + b); }

    bool operator==(const Line &l) const { return a == l.a and b == l.b; }
    bool operator!=(const Line &l) const { return !(*this == l); }
    bool operator<(const Line &l) const {
        return (a == l.a ? a < l.a : b < l.b);
    }

    Line &operator+=(const Line &l) {
        a += l.a;
        b += l.b;
        return *this;
    }
    Line operator+(const Line &l) const { return Line(*this) += l; }
    Line &operator-=(const Line &l) {
        a -= l.a;
        b -= l.b;
        return *this;
    }
    Line operator-(const Line &l) const { return Line(*this) -= l; }
    Line operator-() const { return Line(-a, -b); }

    Line &operator+=(const T &c) {
        b += c;
        return *this;
    }
    Line operator+(const T &c) const { return Line(*this) += c; }
    Line &operator-=(const T &c) {
        b -= c;
        return *this;
    }
    Line operator-(const T &c) const { return Line(*this) -= c; }
    Line &operator*=(const T &c) {
        a *= c;
        b *= c;
        return *this;
    }
    Line operator*(const T &c) const { return Line(*this) *= c; }
    Line &operator/=(const T &c) {
        a /= c;
        b /= c;
        return *this;
    }
    Line operator/(const T &c) const { return Line(*this) /= c; }

    Line inv() const {
        assert(a != 0);
        return Line(T(1) / a, -b / a);
    }

    friend std::istream &operator>>(std::istream &is, Line &l) {
        is >> l.a >> l.b;
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Line &l) {
        if (l.a == 0 and l.b == 0)
            os << 0;
        else if (l.a == 0)
            os << l.b;
        else if (l.b == 0)
            os << l.a << "x";
        else if (l.b > 0)
            os << l.a << "x+" << l.b;
        else
            os << l.a << "x-" << -l.b;
        return os;
    }
};

Back to top page