Geometry: Line
(geometry/line.hpp)

• View this file on GitHub
• Last update: 2026-10-22 22:57:05+09:00
• Include: #include "geometry/line.hpp"

概要

• 直線と線分。

使い方

• geo::line<T>(a, b): 点 a, b を通る直線。
• geo::segment<T>(a, b): 点 a, b を端点とする線分。
• to_line(s): 線分 s を含む直線を返す。
• parallel(l, m), orthogonal(l, m): 直線 l, m が平行か、直交するかを返す。
• on_line(l, p), on_segment(s, p): 点 p が直線 l 上、線分 s 上にあるかを返す。
• intersect(l, m), intersect(l, s), intersect(s, t): 共有点があるかを返す。
• projection(l, p), reflection(l, p): 直線 l への点 p の射影、l に関する p の対称点を返す。
• perpendicular_bisector(a, b): 線分 ab の垂直二等分線を返す。
• dist(x, y): 点、直線、線分の任意の組の距離を返す。
• cross_point(l, m), cross_point(l, s), cross_point(s, t): 交点を返す。交わらないときの動作は未定義。

制約

• projection, reflection, perpendicular_bisector, dist, cross_point は浮動小数点型のみ
• cross_point(l, m) では l, m が平行でない
• cross_point(l, s), cross_point(s, t) では交点がただ 1 つ

Depends on

• Geometry: Point (geometry/point.hpp)

Required by

• Geometry: Circle (geometry/circle.hpp)
• Geometry: Polygon (geometry/polygon.hpp)

Verified with

• test/aoj/CGL_1_A.test.cpp
• test/aoj/CGL_1_B.test.cpp
• test/aoj/CGL_1_C.test.cpp
• test/aoj/CGL_2_A.test.cpp
• test/aoj/CGL_2_B.test.cpp
• test/aoj/CGL_2_C.test.cpp
• test/aoj/CGL_2_D.test.cpp
• test/aoj/CGL_3_A.test.cpp
• test/aoj/CGL_3_B.test.cpp
• test/aoj/CGL_3_C.test.cpp
• test/aoj/CGL_4_A.test.cpp
• test/aoj/CGL_4_B.test.cpp
• test/aoj/CGL_4_C.test.cpp
• test/aoj/CGL_5_A.test.cpp
• test/aoj/CGL_7_A.test.cpp
• test/aoj/CGL_7_B.test.cpp
• test/aoj/CGL_7_C.test.cpp
• test/aoj/CGL_7_D.test.cpp
• test/aoj/CGL_7_E.test.cpp
• test/aoj/CGL_7_F.test.cpp
• test/aoj/CGL_7_G.test.cpp
• test/aoj/CGL_7_H.test.cpp
• test/aoj/CGL_7_I.test.cpp
• test/library-checker/closest_pair.test.cpp
• test/library-checker/static_convex_hull.test.cpp
• test/unit/geometry.test.cpp

Code

#pragma once
#include <algorithm>
#include <cassert>
#include <cmath>
#include <concepts>
#include <iostream>

#include "geometry/point.hpp"
namespace geo {
template <class T> struct line {
    point<T> a, b;
    line() {
    }
    line(const point<T>& a, const point<T>& b) : a(a), b(b) {
    }
    friend std::istream& operator>>(std::istream& is, line& l) {
        return is >> l.a >> l.b;
    }
};
template <class T> struct segment {
    point<T> a, b;
    segment() {
    }
    segment(const point<T>& a, const point<T>& b) : a(a), b(b) {
    }
    friend std::istream& operator>>(std::istream& is, segment& s) {
        return is >> s.a >> s.b;
    }
};
template <class T> line<T> to_line(const segment<T>& s) {
    return line<T>(s.a, s.b);
}
template <class T> bool parallel(const line<T>& l, const line<T>& m) {
    return sgn(cross(l.b - l.a, m.b - m.a)) == 0;
}
template <class T> bool orthogonal(const line<T>& l, const line<T>& m) {
    return sgn(dot(l.b - l.a, m.b - m.a)) == 0;
}
template <class T> bool on_line(const line<T>& l, const point<T>& p) {
    return ccw(l.a, l.b, p) == 0;
}
template <class T> bool on_segment(const segment<T>& s, const point<T>& p) {
    return ccw(s.a, s.b, p) == 0 && sgn(dot(s.a - p, s.b - p)) <= 0;
}
template <class T> bool intersect(const line<T>& l, const line<T>& m) {
    return !parallel(l, m) || on_line(l, m.a);
}
template <class T> bool intersect(const line<T>& l, const segment<T>& s) {
    return ccw(l.a, l.b, s.a) * ccw(l.a, l.b, s.b) <= 0;
}
template <class T> bool intersect(const segment<T>& s, const line<T>& l) {
    return intersect(l, s);
}
template <class T> bool intersect(const segment<T>& s, const segment<T>& t) {
    if (ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) > 0) return false;
    if (ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) > 0) return false;
    if (ccw(s.a, s.b, t.a) != 0 || ccw(s.a, s.b, t.b) != 0) return true;
    return on_segment(s, t.a) || on_segment(s, t.b) || on_segment(t, s.a) || on_segment(t, s.b);
}
template <std::floating_point T> point<T> projection(const line<T>& l, const point<T>& p) {
    point<T> d = l.b - l.a;
    return l.a + d * (dot(d, p - l.a) / norm(d));
}
template <std::floating_point T> point<T> reflection(const line<T>& l, const point<T>& p) {
    return projection(l, p) * T(2) - p;
}
template <std::floating_point T> line<T> perpendicular_bisector(const point<T>& a, const point<T>& b) {
    point<T> m = (a + b) / T(2);
    return line<T>(m, m + normal(b - a));
}
template <std::floating_point T> T dist(const point<T>& a, const point<T>& b) {
    return abs(a - b);
}
template <std::floating_point T> T dist(const line<T>& l, const point<T>& p) {
    return std::abs(cross(l.b - l.a, p - l.a)) / abs(l.b - l.a);
}
template <std::floating_point T> T dist(const point<T>& p, const line<T>& l) {
    return dist(l, p);
}
template <std::floating_point T> T dist(const segment<T>& s, const point<T>& p) {
    if (sgn(dot(s.b - s.a, p - s.a)) < 0) return abs(p - s.a);
    if (sgn(dot(s.a - s.b, p - s.b)) < 0) return abs(p - s.b);
    return dist(to_line(s), p);
}
template <std::floating_point T> T dist(const point<T>& p, const segment<T>& s) {
    return dist(s, p);
}
template <std::floating_point T> T dist(const line<T>& l, const line<T>& m) {
    if (intersect(l, m)) return 0;
    return dist(l, m.a);
}
template <std::floating_point T> T dist(const line<T>& l, const segment<T>& s) {
    if (intersect(l, s)) return 0;
    return std::min(dist(l, s.a), dist(l, s.b));
}
template <std::floating_point T> T dist(const segment<T>& s, const line<T>& l) {
    return dist(l, s);
}
template <std::floating_point T> T dist(const segment<T>& s, const segment<T>& t) {
    if (intersect(s, t)) return 0;
    return std::min({dist(s, t.a), dist(s, t.b), dist(t, s.a), dist(t, s.b)});
}
template <std::floating_point T> point<T> cross_point(const line<T>& l, const line<T>& m) {
    assert(!parallel(l, m));
    point<T> d = l.b - l.a;
    return l.a + d * (cross(m.b - m.a, m.a - l.a) / cross(m.b - m.a, d));
}
template <std::floating_point T> point<T> cross_point(const line<T>& l, const segment<T>& s) {
    assert(intersect(l, s));
    return cross_point(l, to_line(s));
}
template <std::floating_point T> point<T> cross_point(const segment<T>& s, const line<T>& l) {
    return cross_point(l, s);
}
template <std::floating_point T> point<T> cross_point(const segment<T>& s, const segment<T>& t) {
    assert(intersect(s, t));
    return cross_point(to_line(s), to_line(t));
}
}  // namespace geo

#line 2 "geometry/line.hpp"
#include <algorithm>
#include <cassert>
#include <cmath>
#include <concepts>
#include <iostream>

#line 5 "geometry/point.hpp"
#include <type_traits>
namespace geo {
inline long double eps = 1e-9;
template <class T> int sgn(T a) {
    if constexpr (std::is_integral_v<T>) {
        return (a > 0) - (a < 0);
    } else {
        return a < -eps ? -1 : a > eps ? 1 : 0;
    }
}
template <class T> struct point {
    T x, y;
    point() : x(0), y(0) {
    }
    point(T x, T y) : x(x), y(y) {
    }
    point& operator+=(const point& p) {
        x += p.x, y += p.y;
        return *this;
    }
    point& operator-=(const point& p) {
        x -= p.x, y -= p.y;
        return *this;
    }
    point& operator*=(T k) {
        x *= k, y *= k;
        return *this;
    }
    point& operator/=(T k) requires std::floating_point<T> {
        x /= k, y /= k;
        return *this;
    }
    point operator-() const {
        return point(-x, -y);
    }
    friend point operator+(point a, const point& b) {
        return a += b;
    }
    friend point operator-(point a, const point& b) {
        return a -= b;
    }
    friend point operator*(point a, T k) {
        return a *= k;
    }
    friend point operator*(T k, point a) {
        return a *= k;
    }
    friend point operator/(point a, T k) requires std::floating_point<T> {
        return a /= k;
    }
    friend bool operator==(const point& a, const point& b) {
        return sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0;
    }
    friend bool operator!=(const point& a, const point& b) {
        return !(a == b);
    }
    friend bool operator<(const point& a, const point& b) {
        if (sgn(a.x - b.x) != 0) return a.x < b.x;
        return sgn(a.y - b.y) < 0;
    }
    friend bool operator>(const point& a, const point& b) {
        return b < a;
    }
    friend std::istream& operator>>(std::istream& is, point& p) {
        return is >> p.x >> p.y;
    }
    friend std::ostream& operator<<(std::ostream& os, const point& p) {
        return os << p.x << ' ' << p.y;
    }
};
template <class T> T dot(const point<T>& a, const point<T>& b) {
    return a.x * b.x + a.y * b.y;
}
template <class T> T cross(const point<T>& a, const point<T>& b) {
    return a.x * b.y - a.y * b.x;
}
template <class T> T norm(const point<T>& p) {
    return p.x * p.x + p.y * p.y;
}
template <std::floating_point T> T abs(const point<T>& p) {
    return std::sqrt(norm(p));
}
template <std::floating_point T> T arg(const point<T>& p) {
    return std::atan2(p.y, p.x);
}
template <class T> point<T> normal(const point<T>& p) {
    return point<T>(-p.y, p.x);
}
template <std::floating_point T> point<T> unit(const point<T>& p) {
    return p / abs(p);
}
template <std::floating_point T> point<T> rotate(const point<T>& p, T theta) {
    T c = std::cos(theta), s = std::sin(theta);
    return point<T>(p.x * c - p.y * s, p.x * s + p.y * c);
}
template <class T> int ccw(const point<T>& a, const point<T>& b, const point<T>& c) {
    return sgn(cross(b - a, c - a));
}
struct arg_less {
    template <class T> static int group(const point<T>& p) {
        if (sgn(p.y) < 0) return 0;
        if (sgn(p.y) == 0 && sgn(p.x) >= 0) return 1;
        return 2;
    }
    template <class T> bool operator()(const point<T>& a, const point<T>& b) const {
        if (group(a) != group(b)) return group(a) < group(b);
        return sgn(cross(a, b)) > 0;
    }
};
}  // namespace geo
#line 9 "geometry/line.hpp"
namespace geo {
template <class T> struct line {
    point<T> a, b;
    line() {
    }
    line(const point<T>& a, const point<T>& b) : a(a), b(b) {
    }
    friend std::istream& operator>>(std::istream& is, line& l) {
        return is >> l.a >> l.b;
    }
};
template <class T> struct segment {
    point<T> a, b;
    segment() {
    }
    segment(const point<T>& a, const point<T>& b) : a(a), b(b) {
    }
    friend std::istream& operator>>(std::istream& is, segment& s) {
        return is >> s.a >> s.b;
    }
};
template <class T> line<T> to_line(const segment<T>& s) {
    return line<T>(s.a, s.b);
}
template <class T> bool parallel(const line<T>& l, const line<T>& m) {
    return sgn(cross(l.b - l.a, m.b - m.a)) == 0;
}
template <class T> bool orthogonal(const line<T>& l, const line<T>& m) {
    return sgn(dot(l.b - l.a, m.b - m.a)) == 0;
}
template <class T> bool on_line(const line<T>& l, const point<T>& p) {
    return ccw(l.a, l.b, p) == 0;
}
template <class T> bool on_segment(const segment<T>& s, const point<T>& p) {
    return ccw(s.a, s.b, p) == 0 && sgn(dot(s.a - p, s.b - p)) <= 0;
}
template <class T> bool intersect(const line<T>& l, const line<T>& m) {
    return !parallel(l, m) || on_line(l, m.a);
}
template <class T> bool intersect(const line<T>& l, const segment<T>& s) {
    return ccw(l.a, l.b, s.a) * ccw(l.a, l.b, s.b) <= 0;
}
template <class T> bool intersect(const segment<T>& s, const line<T>& l) {
    return intersect(l, s);
}
template <class T> bool intersect(const segment<T>& s, const segment<T>& t) {
    if (ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) > 0) return false;
    if (ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) > 0) return false;
    if (ccw(s.a, s.b, t.a) != 0 || ccw(s.a, s.b, t.b) != 0) return true;
    return on_segment(s, t.a) || on_segment(s, t.b) || on_segment(t, s.a) || on_segment(t, s.b);
}
template <std::floating_point T> point<T> projection(const line<T>& l, const point<T>& p) {
    point<T> d = l.b - l.a;
    return l.a + d * (dot(d, p - l.a) / norm(d));
}
template <std::floating_point T> point<T> reflection(const line<T>& l, const point<T>& p) {
    return projection(l, p) * T(2) - p;
}
template <std::floating_point T> line<T> perpendicular_bisector(const point<T>& a, const point<T>& b) {
    point<T> m = (a + b) / T(2);
    return line<T>(m, m + normal(b - a));
}
template <std::floating_point T> T dist(const point<T>& a, const point<T>& b) {
    return abs(a - b);
}
template <std::floating_point T> T dist(const line<T>& l, const point<T>& p) {
    return std::abs(cross(l.b - l.a, p - l.a)) / abs(l.b - l.a);
}
template <std::floating_point T> T dist(const point<T>& p, const line<T>& l) {
    return dist(l, p);
}
template <std::floating_point T> T dist(const segment<T>& s, const point<T>& p) {
    if (sgn(dot(s.b - s.a, p - s.a)) < 0) return abs(p - s.a);
    if (sgn(dot(s.a - s.b, p - s.b)) < 0) return abs(p - s.b);
    return dist(to_line(s), p);
}
template <std::floating_point T> T dist(const point<T>& p, const segment<T>& s) {
    return dist(s, p);
}
template <std::floating_point T> T dist(const line<T>& l, const line<T>& m) {
    if (intersect(l, m)) return 0;
    return dist(l, m.a);
}
template <std::floating_point T> T dist(const line<T>& l, const segment<T>& s) {
    if (intersect(l, s)) return 0;
    return std::min(dist(l, s.a), dist(l, s.b));
}
template <std::floating_point T> T dist(const segment<T>& s, const line<T>& l) {
    return dist(l, s);
}
template <std::floating_point T> T dist(const segment<T>& s, const segment<T>& t) {
    if (intersect(s, t)) return 0;
    return std::min({dist(s, t.a), dist(s, t.b), dist(t, s.a), dist(t, s.b)});
}
template <std::floating_point T> point<T> cross_point(const line<T>& l, const line<T>& m) {
    assert(!parallel(l, m));
    point<T> d = l.b - l.a;
    return l.a + d * (cross(m.b - m.a, m.a - l.a) / cross(m.b - m.a, d));
}
template <std::floating_point T> point<T> cross_point(const line<T>& l, const segment<T>& s) {
    assert(intersect(l, s));
    return cross_point(l, to_line(s));
}
template <std::floating_point T> point<T> cross_point(const segment<T>& s, const line<T>& l) {
    return cross_point(l, s);
}
template <std::floating_point T> point<T> cross_point(const segment<T>& s, const segment<T>& t) {
    assert(intersect(s, t));
    return cross_point(to_line(s), to_line(t));
}
}  // namespace geo

Back to top page