This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ruthen71/rcpl
#include "geometry/reflection.hpp"
#pragma once #include "geometry/line.hpp" #include "geometry/point.hpp" #include "projection.hpp" // reflection // http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_B template <typename T> Point<T> reflection(const Line<T> &l, const Point<T> &p) { return p + (projection(l, p) - p) * T(2); }
#line 2 "geometry/reflection.hpp" #line 2 "geometry/line.hpp" #line 2 "geometry/point.hpp" // point template <typename T> struct Point { static T EPS; static constexpr T PI = 3.1415926535'8979323846'2643383279L; static void set_eps(const T &e) { EPS = e; } T x, y; Point(const T x = T(0), const T y = T(0)) : 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*=(const Point &p) { return *this = Point(x * p.x - y * p.y, x * p.y + y * p.x); } Point &operator*=(const T &k) { x *= k; y *= k; return *this; } Point &operator/=(const Point &p) { return *this = Point(x * p.x + y * p.y, -x * p.y + y * p.x) / (p.x * p.x + p.y * p.y); } Point &operator/=(const T &k) { x /= k; y /= k; return *this; } Point operator+() const { return *this; } Point operator-() const { return Point(-x, -y); } friend Point operator+(const Point &a, const Point &b) { return Point(a) += b; } friend Point operator-(const Point &a, const Point &b) { return Point(a) -= b; } friend Point operator*(const Point &a, const Point &b) { return Point(a) *= b; } friend Point operator*(const Point &p, const T &k) { return Point(p) *= k; } friend Point operator/(const Point &a, const Point &b) { return Point(a) /= b; } friend Point operator/(const Point &p, const T &k) { return Point(p) /= k; } // for std::set, std::map, compare_arg, ... friend bool operator<(const Point &a, const Point &b) { return a.x == b.x ? a.y < b.y : a.x < b.x; } friend bool operator>(const Point &a, const Point &b) { return a.x == b.x ? a.y > b.y : a.x > b.x; } // I/O 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 template <typename T> inline int sign(const T &x) { return x < -Point<T>::EPS ? -1 : (x > Point<T>::EPS ? 1 : 0); } template <typename T> inline bool equal(const T &a, const T &b) { return sign(a - b) == 0; } template <typename T> inline T radian_to_degree(const T &r) { return r * 180.0 / Point<T>::PI; } template <typename T> inline T degree_to_radian(const T &d) { return d * Point<T>::PI / 180.0; } // contain enum constexpr int IN = 2; constexpr int ON = 1; constexpr int OUT = 0; // equal (point and point) template <typename T> inline bool equal(const Point<T> &a, const Point<T> &b) { return equal(a.x, b.x) and equal(a.y, b.y); } // inner product template <typename T> inline T dot(const Point<T> &a, const Point<T> &b) { return a.x * b.x + a.y * b.y; } // outer product template <typename T> inline T cross(const Point<T> &a, const Point<T> &b) { return a.x * b.y - a.y * b.x; } // rotate Point p counterclockwise by theta radian template <typename T> inline Point<T> rotate(const Point<T> &p, const T &theta) { return p * Point<T>(std::cos(theta), std::sin(theta)); } // compare (x, y) template <typename T> inline bool compare_x(const Point<T> &a, const Point<T> &b) { return equal(a.x, b.x) ? sign(a.y - b.y) < 0 : sign(a.x - b.x) < 0; } // compare (y, x) template <typename T> inline bool compare_y(const Point<T> &a, const Point<T> &b) { return equal(a.y, b.y) ? sign(a.x - b.x) < 0 : sign(a.y - b.y) < 0; } // compare by (arg(p), norm(p)) [0, 360) template <typename T> inline bool compare_arg(const Point<T> &a, const Point<T> &b) { // https://ngtkana.hatenablog.com/entry/2021/11/13/202103 assert(!equal(a, Point<T>(0, 0))); assert(!equal(b, Point<T>(0, 0))); if ((Point<T>(0, 0) < Point<T>(a.y, a.x)) == (Point<T>(0, 0) < Point<T>(b.y, b.x))) { return (a.x * b.y == a.y * b.x) ? norm(a) < norm(b) : a.x * b.y > a.y * b.x; } else { return Point<T>(a.y, a.x) > Point<T>(b.y, b.x); } } // |p| ^ 2 template <typename T> inline T norm(const Point<T> &p) { return p.x * p.x + p.y * p.y; } // |p| template <typename T> inline T abs(const Point<T> &p) { return std::sqrt(norm(p)); } // arg template <typename T> inline T arg(const Point<T> &p) { return std::atan2(p.y, p.x); } // polar template <typename T> inline Point<T> polar(const T &rho, const T &theta = T(0)) { return rotate(Point<T>(rho, 0), theta); } // EPS template <> double Point<double>::EPS = 1e-9; template <> long double Point<long double>::EPS = 1e-12; template <> long long Point<long long>::EPS = 0; template <> __int128_t Point<__int128_t>::EPS = 0; // change EPS // using Double = double; // using Pt = Point<Double>; // Point<Double>::set_eps(new_eps); #line 4 "geometry/line.hpp" // line template <typename T> struct Line { Point<T> a, b; Line() = default; Line(const Point<T> &a, const Point<T> &b) : a(a), b(b) {} // Ax + By = C Line(const T &A, const T &B, const T &C) { assert(!(equal(A, T(0)) and equal(B, T(0)))); if (equal(A, T(0))) { a = Point<T>(T(0), C / B), b = Point<T>(T(1), C / B); } else if (equal(B, T(0))) { a = Point<T>(C / A, T(0)), b = Point<T>(C / A, T(1)); } else if (equal(C, T(0))) { a = Point<T>(T(0), T(0)), b = Point<T>(T(1), B / A); } else { a = Point<T>(T(0), C / B), b = Point<T>(C / A, T(0)); } } friend std::istream &operator>>(std::istream &is, Line &p) { return is >> p.a >> p.b; } friend std::ostream &operator<<(std::ostream &os, const Line &p) { return os << p.a << "->" << p.b; } }; #line 2 "geometry/projection.hpp" #line 5 "geometry/projection.hpp" // projection // http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_A template <typename T> Point<T> projection(const Line<T> &l, const Point<T> &p) { T t = dot(p - l.a, l.b - l.a) / norm(l.b - l.a); return l.a + t * (l.b - l.a); } #line 6 "geometry/reflection.hpp" // reflection // http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_B template <typename T> Point<T> reflection(const Line<T> &l, const Point<T> &p) { return p + (projection(l, p) - p) * T(2); }