直線の方程式

• 直線は $ax + by + c = 0$ を満たす点 $(x, y)$ の集合で表すことができる。
  • 直線の方程式であるから、$a, b$ の少なくとも一方は $0$ ではない。

---

• 与えられた $2$ 点 $(x_1, y_1),\ (x_2, y_2)$ を通る直線の方程式 (ただし $(x_1, y_1) \neq (x_2, y_2)$)
  • $(y_2 - y_1)x + (x_1 - x_2)y + (y_1x_2 - y_2x_1) = 0$
  • https://www.desmos.com/calculator/tt8nqyr3h9
    • $x_1 \neq x_2$ ならば $y = \tfrac{y_2 - y_1}{x_2 - x_1}(x - x_1) + y_1 \Leftrightarrow (y_2 - y_1)x + (x_1 - x_2)y + (y_1x_2 - y_2x_1) = 0$
    • $x_1 = x_2$ ならば $x_1 \neq x_2$ の式にこれを代入すると条件を満たすことが確かめられる。

---

• 直線 $ax + by + c = 0$ に平行なベクトル。
  • 任意の $0$ でない実数 $r$ を使い $r \times (-b, a)$
    • $a \neq 0$ と $b \neq 0$ でそれぞれ方程式を $ x, y$ による関数に変形して適当な $2$ 地点の座標を求める。
      • それぞれの結果は $r \times (-b, a)$ で一致する。

---

• 直線 $ax + by + c = 0$ に垂直なベクトル。
  • 任意の $0$ でない実数 $r$ を使い $r \times (a, b)$
    • 直線に対して平行なベクトル $(-b, a)$ に対する内積が $0$ となるような垂直ベクトルの式を立てる。

---

• 点 $(x_1, y_1)$ を始点としたベクトル $(v_x, v_y)$ とぴったり重なる直線の方程式。
  • $v_yx - v_xy + (v_xy_1 - v_yx_1) = 0$
    • $2$ 点 $(x_1, y_1),\ (x_1 + v_x, y_1 + v_y)$ を通る直線の方程式。

---

• 直線 $ax + by + c = 0$ に対して垂直であって $(x_1, y_1)$ を通る直線の方程式。
  • $bx - ay + (ay_1 - bx_1) = 0$
  • https://www.desmos.com/calculator/9bczgo3jx2
    • 点 $(x_1, y_1)$ を始点とした、元の直線に対する垂直ベクトル $(a, b)$ とぴったり重なる直線の方程式。

---

• $2$ 直線 $a_1x + b_1y + c_1 = 0$ と $a_2x + b_2y + c_2 = 0$ の交点。
  • $a_1b_2 - a_2b_1 \neq 0$ ならば交点は $\left (\tfrac{b_1c_2 - b_2c_1}{a_1b_2 - a_2b_1}, \tfrac{a_1c_2 - a_2c_1}{b_1a_2 - b_2a_1} \right )$

---

• プログラム上で直線を扱う。
  • 方程式 $ax + by + c = 0$ に対して $0$ でない任意の実数を掛けても、表現する直線は変わらない。
    • 直線に対して方程式が一意に定まったほうが都合のいいことが多いので、一意になりそうな条件を付けよう。
  • $\gcd(a, b, c) = 1 \land -(a, b, c) < (a, b, c)$ とか？

template <typename Int>
struct line {
    using int_type = Int;

    // デフォルトでは直線 x = 0
    constexpr line(): line(1, 0, 0) {
    }

    // 直線 ax + by + c = 0 を作成 (ただし一意な表現に変換)
    constexpr line(int_type a_, int_type b_, int_type c_):
            a(a_), b(b_), c(c_) {
        assert(a != 0 || b != 0);

        int_type g = std::gcd(a, std::gcd(b, c));

        a /= g; b /= g; c /= g;
        if (std::make_tuple(a, b, c) < std::make_tuple(-a, -b, -c)) {
            a *= -1; b *= -1; c *= -1;
        }
    }

    // 2 点 (x1, y1), (x2, y2) を通る直線を作成
    constexpr line(int_type x1, int_type y1, int_type x2, int_type y2):
            line(y2 - y1, x1 - x2, y1 * x2 - y2 * x1) {
    }

    // 直線を表現する ax + by + c = 0 について (a, b, c) の tuple を取得
    constexpr auto tuple() const noexcept {
        return std::make_tuple(a, b, c);
    }

    // (x, y) を通る垂直な直線を取得
    constexpr line vert(int_type x, int_type y) const noexcept {
        return line(b, -a, a * y - b * x);
    }

    int_type a, b, c;
};

template <typename Int>
constexpr bool operator ==(const line<Int> &l, const line<Int> &r) noexcept {
    return l.tuple() == r.tuple();
}
template <typename Int>
constexpr bool operator !=(const line<Int> &l, const line<Int> &r) noexcept {
    return l.tuple() != r.tuple();
}

// (a, b, c) の順序を使用することで std::map に line 型が乗るようになる

template <typename Int>
constexpr bool operator <(const line<Int> &l, const line<Int> &r) noexcept {
    return l.tuple() < r.tuple();
}
template <typename Int>
constexpr bool operator >(const line<Int> &l, const line<Int> &r) noexcept {
    return l.tuple() > r.tuple();
}