#pragma once #include <bits/stdc++.h> using namespace std; #include "point.cpp" /* Line */ constexpr long double GEOMETRY_INFTY = 1e9; // 無限遠点 template <typename T> constexpr Point<T> INFTY(GEOMETRY_INFTY, GEOMETRY_INFTY); // 直線 template <typename T> struct Line { Point<T> begin, end; Line() = default; Line(const Point<T> &begin, const Point<T> &end) : begin(begin), end(end) {} constexpr inline Point<T> vec() const { return end - begin; } constexpr inline Point<T> countervec() const { return begin - end; } }; // 半直線 template <typename T> using Ray = Line<T>; // 線分 template <typename T> using Segment = Line<T>; // ll_intersection // 直線同士の交点を返す. template <typename T> Point<T> ll_intersection(const Line<T> &l1, const Line<T> &l2) { if (sgn(cross(l1.vec(), l2.vec())) == 0) return INFTY<T>; // parallel or partially matched return l1.begin + l1.vec() * cross(l2.vec(), l2.begin - l1.begin) / cross(l2.vec(), l1.vec()); // Intersection } // ss_intersection // 線分同士の交点を求める. (線分が交わるかどうか, 交点)を返す. template <typename T> pair<bool, Point<T>> ss_intersection(const Segment<T> &s1, const Segment<T> &s2) { bool is_intersect = (iSP(s2.begin, s1.begin, s1.end) * iSP(s2.end, s1.begin, s1.end) <= 0 && iSP(s1.begin, s2.begin, s2.end) * iSP(s1.end, s2.begin, s2.end) <= 0); return {is_intersect, ll_intersection(s1, s2)}; } // sr_intersection // 線分と半直線の交点を求める. template <typename T> pair<bool, Point<T>> sr_intersection(const Segment<T> &s, const Ray<T> &r) { Point ret = ll_intersection(s, r); if (ret == INFTY<T>) return {false, ret}; Point sv1 = s.begin - ret, sv2 = s.end - ret; Point rv1 = ret - r.begin, rv2 = r.end - r.begin; if (sgn(dot(sv1, sv2)) <= 0 && sgn(dot(rv1, rv2)) > 0) return {true, ret}; return {false, ret}; } // ison // 点pが線分s上の点かどうかを判定する. template <typename T> constexpr inline bool ison(const Point<T> &p, const Segment<T> &s) { return iSP(p, s.begin, s.end) == 0; } // pl_distance // 点pと直線lの距離を求める. template <typename T> long double pl_distance(const Point<T> &p, const Line<T> &l) { return abs((long double)cross(l.vec(), p - l.begin) / length(l.vec())); } // ps_distance // 点pと線分sの距離を求める. template <typename T> long double ps_distance(const Point<T> &p, const Segment<T> &s) { if (sgn(dot(s.vec(), p - s.begin)) < 0 || sgn(dot(s.countervec(), p - s.end)) < 0) { return min(dist(p, s.begin), dist(p, s.end)); } return pl_distance(p, s); } // ss_distance // 線分s1と線分s2の距離を求める. template <typename T> long double ss_distance(const Segment<T> &s1, const Segment<T> &s2) { if (ss_intersection(s1, s2).first) return 0; return min({ps_distance(s1.begin, s2), ps_distance(s1.end, s2), ps_distance(s2.begin, s1), ps_distance(s2.end, s1)}); } // proj // ベクトルpを直線lに射影した点を返す. Point<long double> proj(const Point<long double> &p, const Line<long double> &l) { return l.begin + normalize(l.vec()) * (dot(l.vec(), p - l.begin) / length(l.vec())); } // reflection // ベクトルpを直線lに対して反転させた点を返す. Point<long double> reflection(const Point<long double> &p, const Line<long double> &l) { return proj(p, l) * 2 - p; } // vertical_bisector // 点p,qの垂直二等分線を求める. Line<long double> vertical_bisector(const Point<long double> &p, const Point<long double> &q) { Point mid = (p + q) / 2, vec = rot90(p - q); return Line(mid, mid + vec); } // example: // using P = Point<int>; // using L = Line<int>; // using S = Segment<int>; // using R = Ray<int>; // // using P = Point<long double>; // using L = Line<long double>; // using S = Segment<long double>; // using R = Ray<long double>;
#line 2 "math/line.cpp" #include <bits/stdc++.h> using namespace std; #line 3 "math/point.cpp" using namespace std; constexpr long double GEOMETRY_EPS = 1e-8; // sgn // a > 0なら1, a = 0なら0,a < 0なら-1を返す. constexpr inline int sgn(const long double a) { return (a < -GEOMETRY_EPS ? -1 : (a > GEOMETRY_EPS ? 1 : 0)); } constexpr inline int sgn(const int a) { return (a < 0 ? -1 : (a > 0 ? 1 : 0)); } // 2次元座標クラス // T = int,long doubleなど template <typename T> struct Point { T x, y; constexpr inline Point(T x = 0, T y = 0) : x(x), y(y) {} // unary operator: +,- constexpr inline Point operator+() const { return *this; } constexpr inline Point operator-() const { return Point(-x, -y); } // +=,-=,*=,/= constexpr inline Point &operator+=(const Point &q) { x += q.x; y += q.y; return *this; } constexpr inline Point &operator-=(const Point &q) { x -= q.x; y -= q.y; return *this; } template <typename U> constexpr inline Point &operator*=(U a) { x *= a; y *= a; return *this; } template <typename U> constexpr inline Point &operator/=(U a) { x /= a; y /= a; return *this; } // +,-,*,/ constexpr inline Point operator+(const Point &q) const { return Point(*this) += q; } constexpr inline Point operator-(const Point &q) const { return Point(*this) -= q; } template <typename U> constexpr inline Point operator*(const U &a) const { return Point(*this) *= a; } template <typename U> constexpr inline Point operator/(const U &a) const { return Point(*this) /= a; } // <,> の比較は辞書順の比較, つまりx,yの順に大きい方を確認する. inline bool operator<(const Point &q) const { return (sgn(x - q.x) != 0 ? sgn(x - q.x) < 0 : sgn(y - q.y) < 0); } inline bool operator>(const Point &q) const { return (sgn(x - q.x) != 0 ? sgn(x - q.x) > 0 : sgn(y - q.y) > 0); } inline bool operator==(const Point &q) const { return (sgn(x - q.x) == 0 && sgn(y - q.y) == 0); } friend ostream &operator<<(ostream &os, const Point &p) { return os << p.x << ' ' << p.y; } friend istream &operator>>(istream &is, Point &p) { return is >> p.x >> p.y; } }; // *,/ template <typename T, typename U> inline Point<T> operator*(const U &s, const Point<T> &p) { return {s * p.x, s * p.y}; } template <typename T, typename U> inline Point<T> operator/(const U &s, const Point<T> &p) { return {p.x / s, p.y / s}; } // dot // p,qの内積を計算する. template <typename T> constexpr inline T dot(const Point<T> &p, const Point<T> &q) { return p.x * q.x + p.y * q.y; } // cross // p,qの外積を計算する template <typename T> constexpr inline T cross(const Point<T> &p, const Point<T> &q) { return p.x * q.y - q.x * p.y; } // length2 // ベクトルpの長さ(原点からの距離)の2乗を求める. template <typename T> constexpr inline T length2(const Point<T> &p) { return dot(p, p); } // length // ベクトルpの長さ(原点からの距離)を求める. template <typename T> inline long double length(const Point<T> &p) { return sqrt((long double)length2(p)); } // dist // 点pと点qの間の距離を求める. template <typename T> inline long double dist(const Point<T> &p, const Point<T> &q) { return length(p - q); } // sgn_area // p,q,rがつくる三角形の符号付き面積 template <typename T> constexpr inline long double sgn_area(const Point<T> &p, const Point<T> &q, const Point<T> &r) { return (long double)cross(q - p, r - p) / 2.0; } // area // p,q,rがつくる三角形の面積 template <typename T> constexpr inline long double area(const Point<T> &p, const Point<T> &q, const Point<T> &r) { return abs(sgn_area(p, q, r)); } // normalize // 点pを長さ1に正規化した点を返す. template <typename T> inline Point<long double> normalize(const Point<T> &p) { return (Point<long double>)p / length(p); } // rotation // 点pを反時計回りにargだけ回転させた点を返す. (argはradで測る) template <typename T> inline Point<long double> rotation(const Point<T> &p, double arg) { return Point(cos(arg) * p.x - sin(arg) * p.y, sin(arg) * p.x + cos(arg) * p.y); } // angle // 点pのx軸の正の方向から反時計回りに測った角度を[-pi,pi]で返す. template <typename T> inline long double angle(const Point<T> &p) { return atan2(p.y, p.x); } // rot90 // 点pを反時計回りに90度回転 template <typename T> constexpr inline Point<T> rot90(const Point<T> &p) { return Point(-p.y, p.x); } // iSP // 異なる3点a,b,cの位置関係を返す. template <typename T> int iSP(const Point<T> &a, const Point<T> &b, const Point<T> &c) { if (sgn(cross(c - b, a - b)) > 0) return 1; // ab bc __/: +1 if (sgn(cross(c - b, a - b)) < 0) return -1; // ab bc --\: -1 if (sgn(dot(a - b, c - b)) < 0) return 2; // abc ---: +2 if (sgn(dot(a - c, b - c)) < 0) return -2; // acb ---: -2 return 0; // bac ---: 0 } // example: // using P = Point<int>; // using P = Point<long double>; #line 6 "math/line.cpp" /* Line */ constexpr long double GEOMETRY_INFTY = 1e9; // 無限遠点 template <typename T> constexpr Point<T> INFTY(GEOMETRY_INFTY, GEOMETRY_INFTY); // 直線 template <typename T> struct Line { Point<T> begin, end; Line() = default; Line(const Point<T> &begin, const Point<T> &end) : begin(begin), end(end) {} constexpr inline Point<T> vec() const { return end - begin; } constexpr inline Point<T> countervec() const { return begin - end; } }; // 半直線 template <typename T> using Ray = Line<T>; // 線分 template <typename T> using Segment = Line<T>; // ll_intersection // 直線同士の交点を返す. template <typename T> Point<T> ll_intersection(const Line<T> &l1, const Line<T> &l2) { if (sgn(cross(l1.vec(), l2.vec())) == 0) return INFTY<T>; // parallel or partially matched return l1.begin + l1.vec() * cross(l2.vec(), l2.begin - l1.begin) / cross(l2.vec(), l1.vec()); // Intersection } // ss_intersection // 線分同士の交点を求める. (線分が交わるかどうか, 交点)を返す. template <typename T> pair<bool, Point<T>> ss_intersection(const Segment<T> &s1, const Segment<T> &s2) { bool is_intersect = (iSP(s2.begin, s1.begin, s1.end) * iSP(s2.end, s1.begin, s1.end) <= 0 && iSP(s1.begin, s2.begin, s2.end) * iSP(s1.end, s2.begin, s2.end) <= 0); return {is_intersect, ll_intersection(s1, s2)}; } // sr_intersection // 線分と半直線の交点を求める. template <typename T> pair<bool, Point<T>> sr_intersection(const Segment<T> &s, const Ray<T> &r) { Point ret = ll_intersection(s, r); if (ret == INFTY<T>) return {false, ret}; Point sv1 = s.begin - ret, sv2 = s.end - ret; Point rv1 = ret - r.begin, rv2 = r.end - r.begin; if (sgn(dot(sv1, sv2)) <= 0 && sgn(dot(rv1, rv2)) > 0) return {true, ret}; return {false, ret}; } // ison // 点pが線分s上の点かどうかを判定する. template <typename T> constexpr inline bool ison(const Point<T> &p, const Segment<T> &s) { return iSP(p, s.begin, s.end) == 0; } // pl_distance // 点pと直線lの距離を求める. template <typename T> long double pl_distance(const Point<T> &p, const Line<T> &l) { return abs((long double)cross(l.vec(), p - l.begin) / length(l.vec())); } // ps_distance // 点pと線分sの距離を求める. template <typename T> long double ps_distance(const Point<T> &p, const Segment<T> &s) { if (sgn(dot(s.vec(), p - s.begin)) < 0 || sgn(dot(s.countervec(), p - s.end)) < 0) { return min(dist(p, s.begin), dist(p, s.end)); } return pl_distance(p, s); } // ss_distance // 線分s1と線分s2の距離を求める. template <typename T> long double ss_distance(const Segment<T> &s1, const Segment<T> &s2) { if (ss_intersection(s1, s2).first) return 0; return min({ps_distance(s1.begin, s2), ps_distance(s1.end, s2), ps_distance(s2.begin, s1), ps_distance(s2.end, s1)}); } // proj // ベクトルpを直線lに射影した点を返す. Point<long double> proj(const Point<long double> &p, const Line<long double> &l) { return l.begin + normalize(l.vec()) * (dot(l.vec(), p - l.begin) / length(l.vec())); } // reflection // ベクトルpを直線lに対して反転させた点を返す. Point<long double> reflection(const Point<long double> &p, const Line<long double> &l) { return proj(p, l) * 2 - p; } // vertical_bisector // 点p,qの垂直二等分線を求める. Line<long double> vertical_bisector(const Point<long double> &p, const Point<long double> &q) { Point mid = (p + q) / 2, vec = rot90(p - q); return Line(mid, mid + vec); } // example: // using P = Point<int>; // using L = Line<int>; // using S = Segment<int>; // using R = Ray<int>; // // using P = Point<long double>; // using L = Line<long double>; // using S = Segment<long double>; // using R = Ray<long double>;