proconlib
This documentation is automatically generated by competitive-verifier/competitive-verifier
tools/detail/geometry_2d.hpp
- View this file on GitHub
- Last update: 2025-05-11 22:42:46+09:00
- Include:
#include "tools/detail/geometry_2d.hpp"
Depends on
- std::abs(x) extended for my library (tools/abs.hpp)
- Combine hash values (tools/hash_combine.hpp)
- Check whether T is a monoid (tools/is_monoid.hpp)
- Check whether T is tools::rational (tools/is_rational.hpp)
- std::is_unsigned extended for tools::int128_t and tools::uint128_t (tools/is_unsigned.hpp)
- std::less by key (tools/less_by.hpp)
- The number of nanoseconds that have elapsed since epoch (tools/now.hpp)
- Sign function (tools/signum.hpp)
- $x^2$ under a given monoid (tools/square.hpp)
- Hash of std::tuple (tools/tuple_hash.hpp)
- Vector (tools/vector.hpp)
- Two dimensional vector (tools/vector2.hpp)
Required by
- Two-dimensional circle (tools/circle_2d.hpp)
- Two-dimensional directed line segment (tools/directed_line_segment_2d.hpp)
Two-dimensional half line (tools/half_line_2d.hpp)- Two-dimensional line (tools/line_2d.hpp)
- Two-dimensional polygon (tools/polygon_2d.hpp)
- Two-dimensional triangle (tools/triangle_2d.hpp)
Verified with
- tests/circle_2d/intersection_to_circle.test.cpp
- tests/circle_2d/intersection_to_line.test.cpp
- tests/circle_2d/where/with_radius.test.cpp
- tests/circle_2d/where/without_radius.test.cpp
- tests/directed_line_segment_2d/cross_point.test.cpp
- tests/directed_line_segment_2d/crosses.test.cpp
- tests/directed_line_segment_2d/intersection.test.cpp
- tests/directed_line_segment_2d/squared_distance.test.cpp
- tests/line_2d/is_parallel_to.test.cpp
- tests/line_2d/projection.test.cpp
- tests/polygon_2d/area.test.cpp
- tests/polygon_2d/minimum_bounding_circle.test.cpp
- tests/polygon_2d/where.test.cpp
- tests/triangle_2d/circumcircle.test.cpp
- tests/triangle_2d/incircle.test.cpp
Code
#ifndef TOOLS_DETAIL_GEOMETRY_2D_HPP
#define TOOLS_DETAIL_GEOMETRY_2D_HPP
#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <cstddef>
#include <initializer_list>
#include <limits>
#include <optional>
#include <tuple>
#include <type_traits>
#include <utility>
#include <variant>
#include <vector>
#include "tools/abs.hpp"
#include "tools/is_rational.hpp"
#include "tools/less_by.hpp"
#include "tools/signum.hpp"
#include "tools/square.hpp"
#include "tools/vector2.hpp"
namespace tools {
template <typename T, bool Filled, bool HasRadius = true>
class circle_2d;
template <typename T>
class directed_line_segment_2d;
template <typename T>
class half_line_2d;
template <typename T>
class line_2d;
template <typename T, bool Filled>
class polygon_2d;
template <typename T, bool Filled>
class triangle_2d;
template <typename T, bool Filled, bool HasRadius>
class circle_2d {
::tools::vector2<T> m_center;
T m_radius;
T m_squared_radius;
public:
circle_2d() = default;
circle_2d(const ::tools::vector2<T>& center, const T& radius_or_squared_radius);
template <typename T_ = T, bool Filled_ = Filled>
::std::enable_if_t<::std::is_floating_point_v<T_> && Filled_, T> area() const;
::tools::vector2<T> center() const;
template <bool HasRadius_ = HasRadius>
::std::enable_if_t<HasRadius_, T> radius() const;
T squared_radius() const;
::std::pair<int, int> where(const ::tools::circle_2d<T, Filled, HasRadius>& other) const;
int where(const ::tools::vector2<T>& p) const;
template <typename T_, bool HasRadius_>
friend ::std::enable_if_t<::std::is_floating_point_v<T_>, ::std::optional<::std::variant<::tools::circle_2d<T_, false, HasRadius_>, ::std::vector<::tools::vector2<T_>>>>>
operator&(const ::tools::circle_2d<T_, false, HasRadius_>& lhs, const ::tools::circle_2d<T_, false, HasRadius_>& rhs);
template <typename T_, bool HasRadius_>
friend ::std::enable_if_t<::std::is_floating_point_v<T_>, ::std::vector<::tools::vector2<T_>>>
operator&(const ::tools::circle_2d<T_, false, HasRadius_>& lhs, const ::tools::line_2d<T_>& rhs);
template <typename T_, bool HasRadius_>
friend ::std::enable_if_t<::std::is_floating_point_v<T_>, ::std::optional<::std::variant<::tools::vector2<T_>, ::tools::directed_line_segment_2d<T_>>>>
operator&(const ::tools::circle_2d<T_, true, HasRadius_>& lhs, const ::tools::line_2d<T_>& rhs);
template <typename T_, bool Filled_, bool HasRadius1, bool HasRadius2>
friend bool operator==(const ::tools::circle_2d<T_, Filled_, HasRadius1>& lhs, const ::tools::circle_2d<T_, Filled_, HasRadius2>& rhs);
template <typename T_, bool Filled_, bool HasRadius1, bool HasRadius2>
friend bool operator!=(const ::tools::circle_2d<T_, Filled_, HasRadius1>& lhs, const ::tools::circle_2d<T_, Filled_, HasRadius2>& rhs);
};
template <typename T>
class directed_line_segment_2d {
::tools::vector2<T> m_p1;
::tools::vector2<T> m_p2;
public:
directed_line_segment_2d() = default;
directed_line_segment_2d(const ::tools::vector2<T>& p1, const ::tools::vector2<T>& p2);
bool contains(const ::tools::vector2<T>& p) const;
::std::conditional_t<::std::is_floating_point_v<T>, T, double> length() const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
cross_point(const ::tools::directed_line_segment_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
cross_point(const ::tools::half_line_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
cross_point(const ::tools::line_2d<T>& other) const;
bool crosses(const ::tools::directed_line_segment_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::tools::vector2<T>>
midpoint() const;
const ::tools::vector2<T>& p1() const;
const ::tools::vector2<T>& p2() const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
squared_distance(const ::tools::directed_line_segment_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
squared_distance(const ::tools::half_line_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
squared_distance(const ::tools::line_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
squared_distance(const ::tools::vector2<T>& p) const;
T squared_length() const;
::tools::half_line_2d<T> to_half_line() const;
::tools::line_2d<T> to_line() const;
::tools::vector2<T> to_vector() const;
::tools::directed_line_segment_2d<T> operator+() const;
::tools::directed_line_segment_2d<T> operator-() const;
template <typename T_>
friend ::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::std::variant<::tools::vector2<T_>, ::tools::directed_line_segment_2d<T_>>>>
operator&(const ::tools::directed_line_segment_2d<T_>& lhs, const ::tools::directed_line_segment_2d<T_>& rhs);
template <typename T_>
friend ::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::std::variant<::tools::vector2<T_>, ::tools::directed_line_segment_2d<T_>>>>
operator&(const ::tools::directed_line_segment_2d<T_>& lhs, const ::tools::half_line_2d<T_>& rhs);
template <typename T_>
friend ::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::std::variant<::tools::vector2<T_>, ::tools::directed_line_segment_2d<T_>>>>
operator&(const ::tools::directed_line_segment_2d<T_>& lhs, const ::tools::line_2d<T_>& rhs);
template <typename T_>
friend bool operator==(const ::tools::directed_line_segment_2d<T_>& lhs, const ::tools::directed_line_segment_2d<T_>& rhs);
template <typename T_>
friend bool operator!=(const ::tools::directed_line_segment_2d<T_>& lhs, const ::tools::directed_line_segment_2d<T_>& rhs);
};
template <typename T>
class half_line_2d {
::tools::vector2<T> m_a;
::tools::vector2<T> m_d;
public:
half_line_2d() = default;
half_line_2d(const ::tools::vector2<T>& a, const ::tools::vector2<T>& d);
const ::tools::vector2<T>& a() const;
bool contains(const ::tools::vector2<T>& p) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
cross_point(const ::tools::directed_line_segment_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
cross_point(const ::tools::half_line_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
cross_point(const ::tools::line_2d<T>& other) const;
const ::tools::vector2<T>& d() const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
squared_distance(const ::tools::directed_line_segment_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
squared_distance(const ::tools::half_line_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
squared_distance(const ::tools::line_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
squared_distance(const ::tools::vector2<T>& p) const;
::tools::line_2d<T> to_line() const;
template <typename T_>
friend ::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::std::variant<::tools::vector2<T_>, ::tools::directed_line_segment_2d<T_>>>>
operator&(const ::tools::half_line_2d<T_>& lhs, const ::tools::directed_line_segment_2d<T_>& rhs);
template <typename T_>
friend ::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::std::variant<::tools::vector2<T_>, ::tools::directed_line_segment_2d<T_>, ::tools::half_line_2d<T_>>>>
operator&(const ::tools::half_line_2d<T_>& lhs, const ::tools::half_line_2d<T_>& rhs);
template <typename T_>
friend ::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::std::variant<::tools::vector2<T_>, ::tools::half_line_2d<T_>>>>
operator&(const ::tools::half_line_2d<T_>& lhs, const ::tools::line_2d<T_>& rhs);
template <typename T_>
friend bool operator==(const ::tools::half_line_2d<T_>& lhs, const ::tools::half_line_2d<T_>& rhs);
template <typename T_>
friend bool operator!=(const ::tools::half_line_2d<T_>& lhs, const ::tools::half_line_2d<T_>& rhs);
};
template <typename T>
class line_2d {
T m_a;
T m_b;
T m_c;
public:
line_2d() = default;
line_2d(const T& a, const T& b, const T& c);
const T& a() const;
const T& b() const;
const T& c() const;
bool contains(const ::tools::vector2<T>& p) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
cross_point(const ::tools::directed_line_segment_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
cross_point(const ::tools::half_line_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
cross_point(const ::tools::line_2d<T>& other) const;
bool crosses(const ::tools::line_2d<T>& other) const;
bool is_parallel_to(const ::tools::line_2d<T>& other) const;
::tools::vector2<T> normal() const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::tools::vector2<T>>
projection(const ::tools::vector2<T>& p) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
squared_distance(const ::tools::directed_line_segment_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
squared_distance(const ::tools::half_line_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
squared_distance(const ::tools::line_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
squared_distance(const ::tools::vector2<T>& p) const;
template <typename T_, bool HasRadius_>
friend ::std::enable_if_t<::std::is_floating_point_v<T_>, ::std::vector<::tools::vector2<T_>>>
operator&(const ::tools::line_2d<T_>& lhs, const ::tools::circle_2d<T_, false, HasRadius_>& rhs);
template <typename T_, bool HasRadius_>
friend ::std::enable_if_t<::std::is_floating_point_v<T_>, ::std::optional<::std::variant<::tools::vector2<T_>, ::tools::directed_line_segment_2d<T_>>>>
operator&(const ::tools::line_2d<T_>& lhs, const ::tools::circle_2d<T_, true, HasRadius_>& rhs);
template <typename T_>
friend ::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::std::variant<::tools::vector2<T_>, ::tools::directed_line_segment_2d<T_>>>>
operator&(const ::tools::line_2d<T_>& lhs, const ::tools::directed_line_segment_2d<T_>& rhs);
template <typename T_>
friend ::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::std::variant<::tools::vector2<T_>, ::tools::half_line_2d<T_>>>>
operator&(const ::tools::line_2d<T_>& lhs, const ::tools::half_line_2d<T_>& rhs);
template <typename T_>
friend ::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::std::variant<::tools::vector2<T_>, ::tools::line_2d<T_>>>>
operator&(const ::tools::line_2d<T_>& lhs, const ::tools::line_2d<T_>& rhs);
template <typename T_>
friend bool operator==(const ::tools::line_2d<T_>& lhs, const ::tools::line_2d<T_>& rhs);
template <typename T_>
friend bool operator!=(const ::tools::line_2d<T_>& lhs, const ::tools::line_2d<T_>& rhs);
static ::tools::line_2d<T> through(const ::tools::vector2<T>& p1, const ::tools::vector2<T>& p2);
};
template <typename T, bool Filled>
class polygon_2d {
protected:
::std::vector<::tools::vector2<T>> m_points;
T doubled_signed_area() const;
public:
polygon_2d() = default;
template <typename InputIterator>
polygon_2d(const InputIterator& begin, const InputIterator& end);
polygon_2d(::std::initializer_list<::tools::vector2<T>> init);
template <typename T_ = T, bool Filled_ = Filled>
::std::enable_if_t<(::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>) && Filled_, T> area() const;
template <bool Filled_ = Filled>
::std::enable_if_t<Filled_, T> doubled_area() const;
bool is_counterclockwise() const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::tools::circle_2d<T, Filled, false>> minimum_bounding_circle() const;
int where(const ::tools::vector2<T>& p) const;
};
template <typename T, bool Filled>
class triangle_2d : public polygon_2d<T, Filled> {
template <typename OutputIterator>
void sorted_edges(OutputIterator result) const;
public:
triangle_2d() = default;
template <typename InputIterator>
triangle_2d(const InputIterator& begin, const InputIterator& end);
triangle_2d(::std::initializer_list<::tools::vector2<T>> init);
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::tools::circle_2d<T, Filled, false>> circumcircle() const;
template <typename T_ = T>
::std::enable_if_t<::std::is_floating_point_v<T_>, ::tools::circle_2d<T, Filled>> incircle() const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::tools::circle_2d<T, Filled, false>> minimum_bounding_circle() const;
int type() const;
};
template <typename T, bool Filled, bool HasRadius>
circle_2d<T, Filled, HasRadius>::circle_2d(const ::tools::vector2<T>& center, const T& radius_or_squared_radius) : m_center(center) {
assert(radius_or_squared_radius > T(0));
if constexpr (HasRadius) {
this->m_radius = radius_or_squared_radius;
this->m_squared_radius = ::tools::square(this->m_radius);
} else {
this->m_squared_radius = radius_or_squared_radius;
}
}
template <typename T, bool Filled, bool HasRadius> template <typename T_, bool Filled_>
::std::enable_if_t<::std::is_floating_point_v<T_> && Filled_, T> circle_2d<T, Filled, HasRadius>::area() const {
return ::std::acos(T(-1)) * this->m_squared_radius;
}
template <typename T, bool Filled, bool HasRadius>
::tools::vector2<T> circle_2d<T, Filled, HasRadius>::center() const {
return this->m_center;
}
template <typename T, bool Filled, bool HasRadius> template <bool HasRadius_>
::std::enable_if_t<HasRadius_, T> circle_2d<T, Filled, HasRadius>::radius() const {
return this->m_radius;
}
template <typename T, bool Filled, bool HasRadius>
T circle_2d<T, Filled, HasRadius>::squared_radius() const {
return this->m_squared_radius;
}
template <typename T, bool Filled, bool HasRadius>
::std::pair<int, int> circle_2d<T, Filled, HasRadius>::where(const ::tools::circle_2d<T, Filled, HasRadius>& other) const {
return ::std::make_pair([&]() {
if (*this == other) {
return ::std::numeric_limits<int>::max();
}
if constexpr (HasRadius) {
const auto d2 = (this->m_center - other.m_center).squared_l2_norm();
const auto& a_r = this->m_radius;
const auto& b_r = other.m_radius;
const ::std::array<T, 2> threshold = {::tools::square(a_r - b_r), ::tools::square(a_r + b_r)};
if (d2 < threshold[0]) {
return 0;
} else if (d2 == threshold[0]) {
return 1;
} else if (d2 == threshold[1]) {
return 3;
} else if (threshold[1] < d2) {
return 4;
} else {
return 2;
}
} else {
const auto d2 = (this->m_center - other.m_center).squared_l2_norm();
const auto& a_r2 = this->m_squared_radius;
const auto& b_r2 = other.m_squared_radius;
const auto threshold = a_r2 + b_r2 - d2;
const auto squared_threshold = ::tools::square(threshold);
const auto v = T(4) * a_r2 * b_r2;
if (threshold > T(0) && v < squared_threshold) {
return 0;
} else if (threshold > T(0) && v == squared_threshold) {
return 1;
} else if (threshold < T(0) && v == squared_threshold) {
return 3;
} else if (threshold < T(0) && v < squared_threshold) {
return 4;
} else {
return 2;
}
}
}(), ::tools::signum(this->m_squared_radius - other.m_squared_radius));
}
template <typename T, bool Filled, bool HasRadius>
int circle_2d<T, Filled, HasRadius>::where(const ::tools::vector2<T>& p) const {
return ::tools::signum(this->m_squared_radius - (p - this->m_center).squared_l2_norm());
}
template <typename T, bool HasRadius>
::std::enable_if_t<::std::is_floating_point_v<T>, ::std::optional<::std::variant<::tools::circle_2d<T, false, HasRadius>, ::std::vector<::tools::vector2<T>>>>>
operator&(const ::tools::circle_2d<T, false, HasRadius>& lhs, const ::tools::circle_2d<T, false, HasRadius>& rhs) {
using variant_t = ::std::variant<::tools::circle_2d<T, false, HasRadius>, ::std::vector<::tools::vector2<T>>>;
using result_t = ::std::optional<variant_t>;
const auto t = lhs.where(rhs).first;
if (t == ::std::numeric_limits<int>::max()) return result_t(variant_t(lhs));
if (t == 0 || t == 4) return ::std::nullopt;
const auto& x1 = lhs.m_center.x;
const auto& y1 = lhs.m_center.y;
const auto& x2 = rhs.m_center.x;
const auto& y2 = rhs.m_center.y;
const ::tools::line_2d<T> l(2 * (x2 - x1), 2 * (y2 - y1), (x1 + x2) * (x1 - x2) + (y1 + y2) * (y1 - y2) + rhs.m_squared_radius - lhs.m_squared_radius);
return result_t(variant_t(lhs & l));
}
template <typename T, bool HasRadius>
::std::enable_if_t<::std::is_floating_point_v<T>, ::std::vector<::tools::vector2<T>>>
operator&(const ::tools::circle_2d<T, false, HasRadius>& lhs, const ::tools::line_2d<T>& rhs) {
using result_t = ::std::vector<::tools::vector2<T>>;
if (const auto intersection = ::tools::circle_2d<T, true, HasRadius>(lhs.m_center, HasRadius ? lhs.m_radius : lhs.m_squared_radius) & rhs; intersection) {
struct {
result_t operator()(const ::tools::vector2<T>& v) {
return result_t({v});
}
result_t operator()(const ::tools::directed_line_segment_2d<T>& s) {
return result_t({s.p1(), s.p2()});
}
} visitor;
return ::std::visit(visitor, *intersection);
} else {
return result_t();
}
}
template <typename T, bool HasRadius>
::std::enable_if_t<::std::is_floating_point_v<T>, ::std::optional<::std::variant<::tools::vector2<T>, ::tools::directed_line_segment_2d<T>>>>
operator&(const ::tools::circle_2d<T, true, HasRadius>& lhs, const ::tools::line_2d<T>& rhs) {
using variant_t = ::std::variant<::tools::vector2<T>, ::tools::directed_line_segment_2d<T>>;
using result_t = ::std::optional<variant_t>;
const auto [a, b, c] = (rhs.projection(lhs.m_center) - lhs.m_center).inner_product(rhs.normal()) >= T(0) ? ::std::make_tuple(rhs.a(), rhs.b(), rhs.c()) : ::std::make_tuple(-rhs.a(), -rhs.b(), -rhs.c());
const auto& x = lhs.m_center.x;
const auto& y = lhs.m_center.y;
const auto r = HasRadius ? lhs.m_radius : ::std::sqrt(lhs.m_squared_radius);
const auto& r2 = lhs.m_squared_radius;
const auto d2 = rhs.squared_distance(lhs.m_center);
if (d2 < r2) {
const auto D = ::std::abs(a * x + b * y + c);
return result_t(variant_t(::tools::directed_line_segment_2d<T>(
::tools::vector2<T>((a * D - b * ::std::sqrt((a * a + b * b) * r2 - D * D)) / (a * a + b * b) + x, (b * D + a * ::std::sqrt((a * a + b * b) * r2 - D * D)) / (a * a + b * b) + y),
::tools::vector2<T>((a * D + b * ::std::sqrt((a * a + b * b) * r2 - D * D)) / (a * a + b * b) + x, (b * D - a * ::std::sqrt((a * a + b * b) * r2 - D * D)) / (a * a + b * b) + y)
)));
} else if (d2 == r2) {
return result_t(variant_t(::tools::vector2<T>(a * r / ::std::sqrt(a * a + b * b) + x, b * r / ::std::sqrt(a * a + b * b) + y)));
} else {
return ::std::nullopt;
}
}
template <typename T, bool Filled, bool HasRadius1, bool HasRadius2>
bool operator==(const ::tools::circle_2d<T, Filled, HasRadius1>& lhs, const ::tools::circle_2d<T, Filled, HasRadius2>& rhs) {
return lhs.m_center == rhs.m_center && lhs.m_squared_radius == rhs.m_squared_radius;
}
template <typename T, bool Filled, bool HasRadius1, bool HasRadius2>
bool operator!=(const ::tools::circle_2d<T, Filled, HasRadius1>& lhs, const ::tools::circle_2d<T, Filled, HasRadius2>& rhs) {
return !(lhs == rhs);
}
template <typename T>
directed_line_segment_2d<T>::directed_line_segment_2d(const ::tools::vector2<T>& p1, const ::tools::vector2<T>& p2) :
m_p1(p1),
m_p2(p2) {
assert(p1 != p2);
}
template <typename T>
bool directed_line_segment_2d<T>::contains(const ::tools::vector2<T>& p) const {
if (p == this->m_p1 || p == this->m_p2) return true;
const ::tools::line_2d<T> l = this->to_line();
if (!l.contains(p)) return false;
const T d = (p - this->m_p1).inner_product(this->to_vector());
return T(0) <= d && d <= this->squared_length();
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
directed_line_segment_2d<T>::cross_point(const ::tools::directed_line_segment_2d<T>& other) const {
using result_t = ::std::optional<::tools::vector2<T>>;
const auto intersection = *this & other;
struct {
result_t operator()(const ::tools::vector2<T>& v) {
return result_t(v);
}
result_t operator()(const ::tools::directed_line_segment_2d<T>&) {
return ::std::nullopt;
}
} visitor;
return intersection ? ::std::visit(visitor, *intersection) : ::std::nullopt;
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
directed_line_segment_2d<T>::cross_point(const ::tools::half_line_2d<T>& other) const {
using result_t = ::std::optional<::tools::vector2<T>>;
const auto intersection = *this & other;
struct {
result_t operator()(const ::tools::vector2<T>& v) {
return result_t(v);
}
result_t operator()(const ::tools::directed_line_segment_2d<T>&) {
return ::std::nullopt;
}
} visitor;
return intersection ? ::std::visit(visitor, *intersection) : ::std::nullopt;
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
directed_line_segment_2d<T>::cross_point(const ::tools::line_2d<T>& other) const {
using result_t = ::std::optional<::tools::vector2<T>>;
const auto intersection = *this & other;
struct {
result_t operator()(const ::tools::vector2<T>& v) {
return result_t(v);
}
result_t operator()(const ::tools::directed_line_segment_2d<T>&) {
return result_t();
}
} visitor;
return intersection ? ::std::visit(visitor, *intersection) : ::std::nullopt;
}
template <typename T>
bool directed_line_segment_2d<T>::crosses(const ::tools::directed_line_segment_2d<T>& other) const {
if (this->to_line() == other.to_line()) {
const auto base = this->to_vector();
const auto fixed_other = base.inner_product(other.to_vector()) > T(0) ? other : -other;
const T d1(0);
const T d2 = base.inner_product(base);
const T d3 = base.inner_product(fixed_other.m_p1 - this->m_p1);
const T d4 = base.inner_product(fixed_other.m_p2 - this->m_p1);
return d1 == d4 || d2 == d3;
}
return ::tools::signum(this->to_vector().outer_product(other.m_p1 - this->m_p1)) * ::tools::signum(this->to_vector().outer_product(other.m_p2 - this->m_p1)) <= 0
&& ::tools::signum(other.to_vector().outer_product(this->m_p1 - other.m_p1)) * ::tools::signum(other.to_vector().outer_product(this->m_p2 - other.m_p1)) <= 0;
}
template <typename T>
::std::conditional_t<::std::is_floating_point_v<T>, T, double> directed_line_segment_2d<T>::length() const {
return this->to_vector().l2_norm();
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::tools::vector2<T>>
directed_line_segment_2d<T>::midpoint() const {
return (this->m_p1 + this->m_p2) / T(2);
}
template <typename T>
const ::tools::vector2<T>& directed_line_segment_2d<T>::p1() const {
return this->m_p1;
}
template <typename T>
const ::tools::vector2<T>& directed_line_segment_2d<T>::p2() const {
return this->m_p2;
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
directed_line_segment_2d<T>::squared_distance(const ::tools::directed_line_segment_2d<T>& other) const {
if (*this & other) {
return T(0);
}
return ::std::min({
other.squared_distance(this->m_p1),
other.squared_distance(this->m_p2),
this->squared_distance(other.m_p1),
this->squared_distance(other.m_p2)
});
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
directed_line_segment_2d<T>::squared_distance(const ::tools::half_line_2d<T>& other) const {
if (*this & other) {
return T(0);
}
return ::std::min({
other.squared_distance(this->m_p1),
other.squared_distance(this->m_p2)
});
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
directed_line_segment_2d<T>::squared_distance(const ::tools::line_2d<T>& other) const {
if (*this & other) {
return T(0);
}
return ::std::min({
other.squared_distance(this->m_p1),
other.squared_distance(this->m_p2)
});
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
directed_line_segment_2d<T>::squared_distance(const ::tools::vector2<T>& p) const {
const auto x = this->to_line().projection(p);
const auto d = this->to_vector().inner_product(x - this->m_p1);
return (p - (d < T(0) ? this->m_p1 : this->squared_length() < d ? this->m_p2 : x)).squared_l2_norm();
}
template <typename T>
T directed_line_segment_2d<T>::squared_length() const {
return this->to_vector().squared_l2_norm();
}
template <typename T>
::tools::half_line_2d<T> directed_line_segment_2d<T>::to_half_line() const {
return ::tools::half_line_2d<T>(this->m_p1, this->m_p2 - this->m_p1);
}
template <typename T>
::tools::line_2d<T> directed_line_segment_2d<T>::to_line() const {
return ::tools::line_2d<T>::through(this->m_p1, this->m_p2);
}
template <typename T>
::tools::vector2<T> directed_line_segment_2d<T>::to_vector() const {
return this->m_p2 - this->m_p1;
}
template <typename T>
::tools::directed_line_segment_2d<T> directed_line_segment_2d<T>::operator+() const {
return *this;
}
template <typename T>
::tools::directed_line_segment_2d<T> directed_line_segment_2d<T>::operator-() const {
return ::tools::directed_line_segment_2d<T>(this->m_p2, this->m_p1);
}
template <typename T>
::std::enable_if_t<::tools::is_rational_v<T> || ::std::is_floating_point_v<T>, ::std::optional<::std::variant<::tools::vector2<T>, ::tools::directed_line_segment_2d<T>>>>
operator&(const ::tools::directed_line_segment_2d<T>& lhs, const ::tools::directed_line_segment_2d<T>& rhs) {
using variant_t = ::std::variant<::tools::vector2<T>, ::tools::directed_line_segment_2d<T>>;
using result_t = ::std::optional<variant_t>;
const ::tools::line_2d<T> l1 = lhs.to_line();
const ::tools::line_2d<T> l2 = rhs.to_line();
if (l1 == l2) {
const ::tools::vector2<T> base = lhs.to_vector();
const ::tools::directed_line_segment_2d<T> fixed_rhs = base.inner_product(rhs.to_vector()) > T(0) ? rhs : -rhs;
const T d1(0);
const T d2 = base.inner_product(base);
const T d3 = base.inner_product(fixed_rhs.m_p1 - lhs.m_p1);
const T d4 = base.inner_product(fixed_rhs.m_p2 - lhs.m_p1);
if (d1 == d4) return result_t(variant_t(lhs.m_p1));
if (d2 == d3) return result_t(variant_t(lhs.m_p2));
if (d3 <= d1 && d2 <= d4) return result_t(variant_t(lhs));
if (d1 <= d3 && d4 <= d2) return result_t(variant_t(fixed_rhs));
if (d3 <= d1 && d1 <= d4 && d4 <= d2) return result_t(variant_t(::tools::directed_line_segment_2d<T>(lhs.m_p1, fixed_rhs.m_p2)));
if (d1 <= d3 && d3 <= d2 && d2 <= d4) return result_t(variant_t(::tools::directed_line_segment_2d<T>(fixed_rhs.m_p1, lhs.m_p2)));
return ::std::nullopt;
}
if (l1.is_parallel_to(l2)) return ::std::nullopt;
if (lhs.m_p1 == rhs.m_p1 || lhs.m_p1 == rhs.m_p2) return result_t(variant_t(lhs.m_p1));
if (lhs.m_p2 == rhs.m_p1 || lhs.m_p2 == rhs.m_p2) return result_t(variant_t(lhs.m_p2));
if (
::tools::signum(lhs.to_vector().outer_product(rhs.m_p1 - lhs.m_p1)) * ::tools::signum(lhs.to_vector().outer_product(rhs.m_p2 - lhs.m_p1)) > 0
|| ::tools::signum(rhs.to_vector().outer_product(lhs.m_p1 - rhs.m_p1)) * ::tools::signum(rhs.to_vector().outer_product(lhs.m_p2 - rhs.m_p1)) > 0
) return ::std::nullopt;
return result_t(variant_t(*l1.cross_point(l2)));
}
template <typename T>
::std::enable_if_t<::tools::is_rational_v<T> || ::std::is_floating_point_v<T>, ::std::optional<::std::variant<::tools::vector2<T>, ::tools::directed_line_segment_2d<T>>>>
operator&(const ::tools::directed_line_segment_2d<T>& lhs, const ::tools::half_line_2d<T>& rhs) {
using variant_t = ::std::variant<::tools::vector2<T>, ::tools::directed_line_segment_2d<T>>;
using result_t = ::std::optional<variant_t>;
const ::tools::line_2d<T> l1 = lhs.to_line();
const ::tools::line_2d<T> l2 = rhs.to_line();
if (l1 == l2) {
const bool has_same_direction = rhs.d().inner_product(lhs.to_vector()) > T(0);
const T d1 = rhs.d().inner_product(lhs.m_p1 - rhs.a());
const T d2 = rhs.d().inner_product(lhs.m_p2 - rhs.a());
if (has_same_direction) {
if (d2 < T(0)) return ::std::nullopt;
if (d2 == T(0)) return result_t(variant_t(rhs.a()));
if (d1 < T(0)) return result_t(variant_t(::tools::directed_line_segment_2d<T>(rhs.a(), lhs.m_p2)));
return result_t(variant_t(lhs));
} else {
if (d1 > T(0)) return ::std::nullopt;
if (d1 == T(0)) return result_t(variant_t(rhs.a()));
if (d2 > T(0)) return result_t(variant_t(::tools::directed_line_segment_2d<T>(lhs.m_p1, rhs.a())));
return result_t(variant_t(lhs));
}
}
if (rhs.contains(lhs.m_p1)) return result_t(variant_t(lhs.m_p1));
if (rhs.contains(lhs.m_p2)) return result_t(variant_t(lhs.m_p2));
if ((l2.a() * lhs.m_p1.x + l2.b() * lhs.m_p1.y + l2.c()) * (l2.a() * lhs.m_p2.x + l2.b() * lhs.m_p2.y + l2.c()) > T(0)) return ::std::nullopt;
const ::tools::vector2<T> possible_cross_point = *l1.cross_point(l2);
if (rhs.d().inner_product(possible_cross_point - rhs.a()) < T(0)) return ::std::nullopt;
return result_t(variant_t(possible_cross_point));
}
template <typename T>
::std::enable_if_t<::tools::is_rational_v<T> || ::std::is_floating_point_v<T>, ::std::optional<::std::variant<::tools::vector2<T>, ::tools::directed_line_segment_2d<T>>>>
operator&(const ::tools::directed_line_segment_2d<T>& lhs, const ::tools::line_2d<T>& rhs) {
using variant_t = ::std::variant<::tools::vector2<T>, ::tools::directed_line_segment_2d<T>>;
using result_t = ::std::optional<variant_t>;
const ::tools::line_2d<T> lhs_line = lhs.to_line();
if (lhs_line == rhs) return result_t(variant_t(lhs));
if (rhs.contains(lhs.m_p1)) return result_t(variant_t(lhs.m_p1));
if (rhs.contains(lhs.m_p2)) return result_t(variant_t(lhs.m_p2));
if ((rhs.a() * lhs.m_p1.x + rhs.b() * lhs.m_p1.y + rhs.c()) * (rhs.a() * lhs.m_p2.x + rhs.b() * lhs.m_p2.y + rhs.c()) > T(0)) return ::std::nullopt;
return result_t(variant_t(*lhs_line.cross_point(rhs)));
}
template <typename T>
bool operator==(const ::tools::directed_line_segment_2d<T>& lhs, const ::tools::directed_line_segment_2d<T>& rhs) {
return lhs.p1() == rhs.p1() && lhs.p2() == rhs.p2();
}
template <typename T>
bool operator!=(const ::tools::directed_line_segment_2d<T>& lhs, const ::tools::directed_line_segment_2d<T>& rhs) {
return !(lhs == rhs);
}
template <typename T>
half_line_2d<T>::half_line_2d(const ::tools::vector2<T>& a, const ::tools::vector2<T>& d) :
m_a(a),
m_d(d) {
assert(d != ::tools::vector2<T>(T(0), T(0)));
}
template <typename T>
const ::tools::vector2<T>& half_line_2d<T>::a() const {
return this->m_a;
}
template <typename T>
bool half_line_2d<T>::contains(const ::tools::vector2<T>& p) const {
const ::tools::line_2d<T> l = this->to_line();
return l.a() * p.x + l.b() * p.y + l.c() == T(0) && this->m_d.inner_product(p - this->m_a) >= T(0);
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
half_line_2d<T>::cross_point(const ::tools::directed_line_segment_2d<T>& other) const {
return other.cross_point(*this);
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
half_line_2d<T>::cross_point(const ::tools::half_line_2d<T>& other) const {
using result_t = ::std::optional<::tools::vector2<T>>;
const auto intersection = *this & other;
struct {
result_t operator()(const ::tools::vector2<T>& v) {
return result_t(v);
}
result_t operator()(const ::tools::directed_line_segment_2d<T>&) {
return ::std::nullopt;
}
result_t operator()(const ::tools::half_line_2d<T>&) {
return ::std::nullopt;
}
} visitor;
return intersection ? ::std::visit(visitor, *intersection) : ::std::nullopt;
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
half_line_2d<T>::cross_point(const ::tools::line_2d<T>& other) const {
using result_t = ::std::optional<::tools::vector2<T>>;
const auto intersection = *this & other;
struct {
result_t operator()(const ::tools::vector2<T>& v) {
return result_t(v);
}
result_t operator()(const ::tools::half_line_2d<T>&) {
return ::std::nullopt;
}
} visitor;
return intersection ? ::std::visit(visitor, *intersection) : ::std::nullopt;
}
template <typename T>
const ::tools::vector2<T>& half_line_2d<T>::d() const {
return this->m_d;
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
half_line_2d<T>::squared_distance(const ::tools::directed_line_segment_2d<T>& other) const {
return other.squared_distance(*this);
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
half_line_2d<T>::squared_distance(const ::tools::half_line_2d<T>& other) const {
if (*this & other) {
return T(0);
}
if (const auto x = this->to_line().cross_point(other.to_line()); x) {
if (this->m_d.inner_product(*x - this->m_a) >= T(0)) {
return (other.m_a - *x).squared_l2_norm();
} else if (other.m_d.inner_product(*x - other.m_a) >= T(0)) {
return (this->m_a - *x).squared_l2_norm();
} else {
return (this->m_a - other.m_a).squared_l2_norm();
}
} else {
if (this->m_d.inner_product(other.m_a) > T(0)) {
return this->to_line().squared_distance(other.to_line());
} else if (const auto x = this->to_line().projection(other.m_a); this->m_d.inner_product(x - this->m_a) >= T(0)) {
return this->to_line().squared_distance(other.to_line());
} else {
return (this->m_a - other.m_a).squared_l2_norm();
}
}
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
half_line_2d<T>::squared_distance(const ::tools::line_2d<T>& other) const {
if (*this & other) {
return T(0);
}
return other.squared_distance(this->m_a);
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
half_line_2d<T>::squared_distance(const ::tools::vector2<T>& p) const {
auto x = this->to_line().projection(p);
const auto d = this->m_d.inner_product(x - this->m_a);
return (p - (d < T(0) ? this->m_a : x)).squared_l2_norm();
}
template <typename T>
::tools::line_2d<T> half_line_2d<T>::to_line() const {
return ::tools::line_2d<T>::through(this->m_a, this->m_a + this->m_d);
}
template <typename T>
::std::enable_if_t<::tools::is_rational_v<T> || ::std::is_floating_point_v<T>, ::std::optional<::std::variant<::tools::vector2<T>, ::tools::directed_line_segment_2d<T>>>>
operator&(const ::tools::half_line_2d<T>& lhs, const ::tools::directed_line_segment_2d<T>& rhs) {
return rhs & lhs;
}
template <typename T>
::std::enable_if_t<::tools::is_rational_v<T> || ::std::is_floating_point_v<T>, ::std::optional<::std::variant<::tools::vector2<T>, ::tools::directed_line_segment_2d<T>, ::tools::half_line_2d<T>>>>
operator&(const ::tools::half_line_2d<T>& lhs, const ::tools::half_line_2d<T>& rhs) {
using variant_t = ::std::variant<::tools::vector2<T>, ::tools::directed_line_segment_2d<T>, ::tools::half_line_2d<T>>;
using result_t = ::std::optional<variant_t>;
const ::tools::line_2d<T> l1 = lhs.to_line();
const ::tools::line_2d<T> l2 = rhs.to_line();
if (l1 == l2) {
if (lhs.d().inner_product(rhs.d()) > T(0)) {
switch (::tools::signum(lhs.d().inner_product(rhs.a() - lhs.a()))) {
case 1:
case 0:
return result_t(variant_t(rhs));
default:
return result_t(variant_t(lhs));
}
} else {
switch (::tools::signum(lhs.d().inner_product(rhs.a() - lhs.a()))) {
case 1:
return result_t(variant_t(::tools::directed_line_segment_2d<T>(lhs.a(), rhs.a())));
case 0:
return result_t(variant_t(lhs.a()));
default:
return ::std::nullopt;
}
}
} else if (l1.is_parallel_to(l2)) {
return ::std::nullopt;
} else {
const ::tools::vector2<T> possible_cross_point = *l1.cross_point(l2);
if (lhs.d().inner_product(possible_cross_point - lhs.a()) < T(0) || rhs.d().inner_product(possible_cross_point - rhs.a()) < T(0)) {
return ::std::nullopt;
}
return result_t(variant_t(possible_cross_point));
}
}
template <typename T>
::std::enable_if_t<::tools::is_rational_v<T> || ::std::is_floating_point_v<T>, ::std::optional<::std::variant<::tools::vector2<T>, ::tools::half_line_2d<T>>>>
operator&(const ::tools::half_line_2d<T>& lhs, const ::tools::line_2d<T>& rhs) {
using variant_t = ::std::variant<::tools::vector2<T>, ::tools::half_line_2d<T>>;
using result_t = ::std::optional<variant_t>;
const auto lhs_line = lhs.to_line();
if (lhs_line == rhs) return result_t(variant_t(lhs));
const auto possible_cross_point = lhs_line.cross_point(rhs);
return possible_cross_point && lhs.m_d.inner_product(*possible_cross_point - lhs.m_a) >= T(0)
? result_t(variant_t(*possible_cross_point))
: ::std::nullopt;
}
template <typename T>
bool operator==(const ::tools::half_line_2d<T>& lhs, const ::tools::half_line_2d<T>& rhs) {
return lhs.a() == rhs.a() && lhs.d().x * rhs.d().y == rhs.d().x * lhs.d().y;
}
template <typename T>
bool operator!=(const ::tools::half_line_2d<T>& lhs, const ::tools::half_line_2d<T>& rhs) {
return !(lhs == rhs);
}
template <typename T>
line_2d<T>::line_2d(const T& a, const T& b, const T& c) :
m_a(a),
m_b(b),
m_c(c) {
assert(a != T(0) || b != T(0));
}
template <typename T>
const T& line_2d<T>::a() const {
return this->m_a;
}
template <typename T>
const T& line_2d<T>::b() const {
return this->m_b;
}
template <typename T>
const T& line_2d<T>::c() const {
return this->m_c;
}
template <typename T>
bool line_2d<T>::contains(const ::tools::vector2<T>& p) const {
return this->m_a * p.x + this->m_b * p.y + this->m_c == T(0);
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
line_2d<T>::cross_point(const ::tools::directed_line_segment_2d<T>& other) const {
return other.cross_point(*this);
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
line_2d<T>::cross_point(const ::tools::half_line_2d<T>& other) const {
return other.cross_point(*this);
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
line_2d<T>::cross_point(const ::tools::line_2d<T>& other) const {
using result_t = ::std::optional<::tools::vector2<T>>;
if (!this->crosses(other)) return ::std::nullopt;
return result_t(::tools::vector2<T>(
(this->m_b * other.m_c - other.m_b * this->m_c) / (this->m_a * other.m_b - other.m_a * this->m_b),
(other.m_a * this->m_c - this->m_a * other.m_c) / (this->m_a * other.m_b - other.m_a * this->m_b)
));
}
template <typename T>
bool line_2d<T>::crosses(const ::tools::line_2d<T>& other) const {
return this->m_a * other.m_b != other.m_a * this->m_b;
}
template <typename T>
bool line_2d<T>::is_parallel_to(const ::tools::line_2d<T>& other) const {
return this->m_a * other.m_b == this->m_b * other.m_a;
}
template <typename T>
::tools::vector2<T> line_2d<T>::normal() const {
return ::tools::vector2<T>(this->m_a, this->m_b);
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::tools::vector2<T>>
line_2d<T>::projection(const ::tools::vector2<T>& p) const {
return *::tools::half_line_2d<T>(p, this->normal()).to_line().cross_point(*this);
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
line_2d<T>::squared_distance(const ::tools::directed_line_segment_2d<T>& other) const {
return other.squared_distance(*this);
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
line_2d<T>::squared_distance(const ::tools::half_line_2d<T>& other) const {
return other.squared_distance(*this);
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
line_2d<T>::squared_distance(const ::tools::line_2d<T>& other) const {
if (this->is_parallel_to(other)) {
return ::tools::square(other.m_a * this->m_c - this->m_a * other.m_c) / (::tools::square(this->m_a) + ::tools::square(this->m_b)) / ::tools::square(other.m_a);
} else {
return T(0);
}
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
line_2d<T>::squared_distance(const ::tools::vector2<T>& p) const {
return (p - this->projection(p)).squared_l2_norm();
}
template <typename T, bool HasRadius>
::std::enable_if_t<::std::is_floating_point_v<T>, ::std::vector<::tools::vector2<T>>>
operator&(const ::tools::line_2d<T>& lhs, const ::tools::circle_2d<T, false, HasRadius>& rhs) {
return rhs & lhs;
}
template <typename T, bool HasRadius>
::std::enable_if_t<::std::is_floating_point_v<T>, ::std::optional<::std::variant<::tools::vector2<T>, ::tools::directed_line_segment_2d<T>>>>
operator&(const ::tools::line_2d<T>& lhs, const ::tools::circle_2d<T, true, HasRadius>& rhs) {
return rhs & lhs;
}
template <typename T>
::std::enable_if_t<::tools::is_rational_v<T> || ::std::is_floating_point_v<T>, ::std::optional<::std::variant<::tools::vector2<T>, ::tools::directed_line_segment_2d<T>>>>
operator&(const ::tools::line_2d<T>& lhs, const ::tools::directed_line_segment_2d<T>& rhs) {
return rhs & lhs;
}
template <typename T>
::std::enable_if_t<::tools::is_rational_v<T> || ::std::is_floating_point_v<T>, ::std::optional<::std::variant<::tools::vector2<T>, ::tools::half_line_2d<T>>>>
operator&(const ::tools::line_2d<T>& lhs, const ::tools::half_line_2d<T>& rhs) {
return rhs & lhs;
}
template <typename T>
::std::enable_if_t<::tools::is_rational_v<T> || ::std::is_floating_point_v<T>, ::std::optional<::std::variant<::tools::vector2<T>, ::tools::line_2d<T>>>>
operator&(const ::tools::line_2d<T>& lhs, const ::tools::line_2d<T>& rhs) {
using variant_t = ::std::variant<::tools::vector2<T>, ::tools::line_2d<T>>;
using result_t = ::std::optional<variant_t>;
if (lhs == rhs) return result_t(variant_t(lhs));
const auto possible_cross_point = lhs.cross_point(rhs);
return possible_cross_point ? result_t(variant_t(*possible_cross_point)) : ::std::nullopt;
}
template <typename T>
bool operator==(const ::tools::line_2d<T>& lhs, const ::tools::line_2d<T>& rhs) {
return lhs.m_b * rhs.m_c == lhs.m_c * rhs.m_b && lhs.m_c * rhs.m_a == lhs.m_a * rhs.m_c && lhs.m_a * rhs.m_b == lhs.m_b * rhs.m_a;
}
template <typename T>
bool operator!=(const ::tools::line_2d<T>& lhs, const ::tools::line_2d<T>& rhs) {
return !(lhs == rhs);
}
template <typename T>
::tools::line_2d<T> line_2d<T>::through(const ::tools::vector2<T>& p1, const ::tools::vector2<T>& p2) {
return ::tools::line_2d<T>(p1.y - p2.y, p2.x - p1.x, (p2.y - p1.y) * p1.x - (p2.x - p1.x) * p1.y);
}
template <typename T, bool Filled>
T polygon_2d<T, Filled>::doubled_signed_area() const {
T result(0);
for (::std::size_t i = 0; i < this->m_points.size(); ++i) {
result += (this->m_points[i].x - this->m_points[(i + 1) % this->m_points.size()].x) * (this->m_points[i].y + this->m_points[(i + 1) % this->m_points.size()].y);
}
return result;
}
template <typename T, bool Filled>
template <typename InputIterator>
polygon_2d<T, Filled>::polygon_2d(const InputIterator& begin, const InputIterator& end) : m_points(begin, end) {
assert(this->m_points.size() >= 3);
}
template <typename T, bool Filled>
polygon_2d<T, Filled>::polygon_2d(::std::initializer_list<::tools::vector2<T>> init) : polygon_2d(init.begin(), init.end()) {
}
template <typename T, bool Filled> template <typename T_, bool Filled_>
::std::enable_if_t<(::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>) && Filled_, T> polygon_2d<T, Filled>::area() const {
return this->doubled_area() / T(2);
}
template <typename T, bool Filled> template <bool Filled_>
::std::enable_if_t<Filled_, T> polygon_2d<T, Filled>::doubled_area() const {
return ::tools::abs(this->doubled_signed_area());
}
template <typename T, bool Filled>
bool polygon_2d<T, Filled>::is_counterclockwise() const {
return this->doubled_signed_area() > T(0);
}
template <typename T, bool Filled> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::tools::circle_2d<T, Filled, false>> polygon_2d<T, Filled>::minimum_bounding_circle() const {
::std::optional<::tools::circle_2d<T, Filled, false>> answer;
for (::std::size_t i = 0; i < this->m_points.size(); ++i) {
for (::std::size_t j = i + 1; j < this->m_points.size(); ++j) {
for (::std::size_t k = j + 1; k < this->m_points.size(); ++k) {
if (const auto possible_answer = ::tools::triangle_2d<T, Filled>({this->m_points[i], this->m_points[j], this->m_points[k]}).minimum_bounding_circle();
!answer || answer->squared_radius() < possible_answer.squared_radius()) {
answer = ::std::move(possible_answer);
}
}
}
}
return *answer;
}
template <typename T, bool Filled>
int polygon_2d<T, Filled>::where(const ::tools::vector2<T>& p) const {
::std::vector<::tools::directed_line_segment_2d<T>> edges;
for (::std::size_t i = 0; i < this->m_points.size(); ++i) {
edges.emplace_back(this->m_points[i], this->m_points[(i + 1) % this->m_points.size()]);
}
if (std::any_of(edges.begin(), edges.end(), [&](const auto& edge) { return edge.contains(p); })) {
return 0;
} else {
bool in = false;
for (const auto& edge : edges) {
if ([&]() {
const auto l = edge.to_line();
if (l == ::tools::line_2d<T>(T(0), T(1), -p.y)) return false;
if (p.x <= edge.p1().x && p.y == edge.p1().y) return edge.p2().y < edge.p1().y;
if (p.x <= edge.p2().x && p.y == edge.p2().y) return edge.p1().y < edge.p2().y;
if ((edge.p1().y - p.y) * (edge.p2().y - p.y) > T(0)) return false;
return l.a() * (l.a() * p.x + l.b() * p.y + l.c()) < T(0);
}()) {
in = !in;
}
}
return in ? 1 : -1;
}
}
template <typename T, bool Filled>
template <typename OutputIterator>
void triangle_2d<T, Filled>::sorted_edges(OutputIterator result) const {
::std::array<::tools::directed_line_segment_2d<T>, 3> edges;
for (int i = 0; i < 3; ++i) {
edges[i] = ::tools::directed_line_segment_2d<T>(this->m_points[i], this->m_points[(i + 1) % 3]);
}
::std::sort(edges.begin(), edges.end(), ::tools::less_by([](const auto& edge) {
return edge.squared_length();
}));
for (const auto& edge : edges) {
*result = edge;
++result;
}
}
template <typename T, bool Filled>
template <typename InputIterator>
triangle_2d<T, Filled>::triangle_2d(const InputIterator& begin, const InputIterator& end) : polygon_2d<T, Filled>(begin, end) {
assert(this->m_points.size() == 3);
}
template <typename T, bool Filled>
triangle_2d<T, Filled>::triangle_2d(::std::initializer_list<::tools::vector2<T>> init) : triangle_2d(init.begin(), init.end()) {
}
template <typename T, bool Filled> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::tools::circle_2d<T, Filled, false>> triangle_2d<T, Filled>::circumcircle() const {
const auto& A = this->m_points[0];
const auto& B = this->m_points[1];
const auto& C = this->m_points[2];
const auto a2 = (C - B).squared_l2_norm();
const auto b2 = (A - C).squared_l2_norm();
const auto c2 = (B - A).squared_l2_norm();
const auto kA = a2 * (b2 + c2 - a2);
const auto kB = b2 * (c2 + a2 - b2);
const auto kC = c2 * (a2 + b2 - c2);
const auto circumcenter = (kA * A + kB * B + kC * C) / (kA + kB + kC);
return ::tools::circle_2d<T, Filled, false>(circumcenter, (circumcenter - A).squared_l2_norm());
}
template <typename T, bool Filled> template <typename T_>
::std::enable_if_t<::std::is_floating_point_v<T_>, ::tools::circle_2d<T, Filled>> triangle_2d<T, Filled>::incircle() const {
const auto& A = this->m_points[0];
const auto& B = this->m_points[1];
const auto& C = this->m_points[2];
const auto a = (C - B).l2_norm();
const auto b = (A - C).l2_norm();
const auto c = (B - A).l2_norm();
const auto incenter = (a * A + b * B + c * C) / (a + b + c);
return ::tools::circle_2d<T, Filled>(incenter, ::tools::abs(this->doubled_signed_area()) / (a + b + c));
}
template <typename T, bool Filled> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::tools::circle_2d<T, Filled, false>> triangle_2d<T, Filled>::minimum_bounding_circle() const {
::std::array<::tools::directed_line_segment_2d<T>, 3> edges;
this->sorted_edges(edges.begin());
if (edges[0].squared_length() + edges[1].squared_length() <= edges[2].squared_length()) {
const auto center = edges[2].midpoint();
return ::tools::circle_2d<T, Filled, false>(center, (center - edges[2].p1()).squared_l2_norm());
} else {
return this->circumcircle();
}
}
template <typename T, bool Filled>
int triangle_2d<T, Filled>::type() const {
::std::array<::tools::directed_line_segment_2d<T>, 3> edges;
this->sorted_edges(edges.begin());
const auto c2 = edges[2].squared_length();
const auto a2b2 = edges[1].squared_length() + edges[0].squared_length();
if (c2 < a2b2) {
return 0;
} else if (c2 == a2b2) {
return 1;
} else {
return 2;
}
}
}
#endif
#line 1 "tools/detail/geometry_2d.hpp"
#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <cstddef>
#include <initializer_list>
#include <limits>
#include <optional>
#include <tuple>
#include <type_traits>
#include <utility>
#include <variant>
#include <vector>
#line 1 "tools/abs.hpp"
namespace tools {
constexpr float abs(const float x) {
return x < 0 ? -x : x;
}
constexpr double abs(const double x) {
return x < 0 ? -x : x;
}
constexpr long double abs(const long double x) {
return x < 0 ? -x : x;
}
constexpr int abs(const int x) {
return x < 0 ? -x : x;
}
constexpr long abs(const long x) {
return x < 0 ? -x : x;
}
constexpr long long abs(const long long x) {
return x < 0 ? -x : x;
}
constexpr unsigned int abs(const unsigned int x) {
return x;
}
constexpr unsigned long abs(const unsigned long x) {
return x;
}
constexpr unsigned long long abs(const unsigned long long x) {
return x;
}
}
#line 1 "tools/is_rational.hpp"
#line 5 "tools/is_rational.hpp"
namespace tools {
template <typename T>
struct is_rational : std::false_type {};
template <typename T>
inline constexpr bool is_rational_v = ::tools::is_rational<T>::value;
}
#line 1 "tools/less_by.hpp"
namespace tools {
template <class F>
class less_by {
private:
F selector;
public:
less_by(const F& selector) : selector(selector) {
}
template <class T>
bool operator()(const T& x, const T& y) const {
return selector(x) < selector(y);
}
};
}
#line 1 "tools/signum.hpp"
#line 1 "tools/is_unsigned.hpp"
#line 5 "tools/is_unsigned.hpp"
namespace tools {
template <typename T>
struct is_unsigned : ::std::is_unsigned<T> {};
template <typename T>
inline constexpr bool is_unsigned_v = ::tools::is_unsigned<T>::value;
}
#line 5 "tools/signum.hpp"
namespace tools {
template <typename T>
constexpr int signum(const T x) noexcept {
if constexpr (::tools::is_unsigned_v<T>) {
return T(0) < x;
} else {
return (T(0) < x) - (x < T(0));
}
}
}
#line 1 "tools/square.hpp"
#line 1 "tools/is_monoid.hpp"
#line 6 "tools/is_monoid.hpp"
namespace tools {
template <typename M, typename = void>
struct is_monoid : ::std::false_type {};
template <typename M>
struct is_monoid<M, ::std::enable_if_t<
::std::is_same_v<typename M::T, decltype(M::op(::std::declval<typename M::T>(), ::std::declval<typename M::T>()))> &&
::std::is_same_v<typename M::T, decltype(M::e())>
, void>> : ::std::true_type {};
template <typename M>
inline constexpr bool is_monoid_v = ::tools::is_monoid<M>::value;
}
#line 6 "tools/square.hpp"
namespace tools {
template <typename M>
::std::enable_if_t<::tools::is_monoid_v<M>, typename M::T> square(const typename M::T& x) {
return M::op(x, x);
}
template <typename T>
::std::enable_if_t<!::tools::is_monoid_v<T>, T> square(const T& x) {
return x * x;
}
}
#line 1 "tools/vector2.hpp"
#line 1 "tools/vector.hpp"
#line 11 "tools/vector.hpp"
#include <iterator>
#line 15 "tools/vector.hpp"
#include <iostream>
#include <string>
#include <functional>
#line 1 "tools/tuple_hash.hpp"
#line 1 "tools/now.hpp"
#include <chrono>
namespace tools {
inline long long now() {
return ::std::chrono::duration_cast<::std::chrono::nanoseconds>(::std::chrono::high_resolution_clock::now().time_since_epoch()).count();
}
}
#line 1 "tools/hash_combine.hpp"
#line 6 "tools/hash_combine.hpp"
// Source: https://github.com/google/cityhash/blob/f5dc54147fcce12cefd16548c8e760d68ac04226/src/city.h
// License: MIT
// Author: Google Inc.
// Copyright (c) 2011 Google, Inc.
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
namespace tools {
template <typename T>
void hash_combine(::std::size_t& seed, const T& v) {
static const ::std::hash<T> hasher;
static constexpr ::std::size_t k_mul = 0x9ddfea08eb382d69ULL;
::std::size_t a = (hasher(v) ^ seed) * k_mul;
a ^= (a >> 47);
::std::size_t b = (seed ^ a) * k_mul;
b ^= (b >> 47);
seed = b * k_mul;
}
}
#line 11 "tools/tuple_hash.hpp"
namespace tools {
template <typename... Ts>
struct tuple_hash {
template <::std::size_t I = sizeof...(Ts) - 1>
::std::size_t operator()(const ::std::tuple<Ts...>& key) const {
if constexpr (I == ::std::numeric_limits<::std::size_t>::max()) {
static const ::std::size_t seed = ::tools::now();
return seed;
} else {
::std::size_t seed = this->operator()<I - 1>(key);
::tools::hash_combine(seed, ::std::get<I>(key));
return seed;
}
}
};
}
#line 21 "tools/vector.hpp"
namespace tools {
namespace detail {
namespace vector {
template <typename T, ::std::size_t N>
class members {
protected:
constexpr static bool variable_sized = false;
constexpr static bool has_aliases = false;
::std::array<T, N> m_values;
members() : m_values() {}
members(const ::std::initializer_list<T> il) : m_values(il) {
assert(il.size() == N);
}
};
template <typename T>
class members<T, 2> {
protected:
constexpr static bool variable_sized = false;
constexpr static bool has_aliases = true;
::std::array<T*, 2> m_values;
members() : m_values{&this->x, &this->y} {}
members(const T& x, const T& y) : m_values{&this->x, &this->y}, x(x), y(y) {}
members(const ::std::initializer_list<T> il) : m_values{&this->x, &this->y}, x(il.begin()[0]), y(il.begin()[1]) {
assert(il.size() == 2);
}
public:
T x;
T y;
};
template <typename T>
class members<T, 3> {
protected:
constexpr static bool variable_sized = false;
constexpr static bool has_aliases = true;
::std::array<T*, 3> m_values;
members() : m_values{&this->x, &this->y, &this->z} {}
members(const T& x, const T& y, const T& z) : m_values{&this->x, &this->y, &this->z}, x(x), y(y), z(z) {}
members(const ::std::initializer_list<T> il) : m_values{&this->x, &this->y, &this->z}, x(il.begin()[0]), y(il.begin()[1]), z(il.begin()[2]) {
assert(il.size() == 3);
}
public:
T x;
T y;
T z;
};
template <typename T>
class members<T, 4> {
protected:
constexpr static bool variable_sized = false;
constexpr static bool has_aliases = true;
::std::array<T*, 4> m_values;
members() : m_values{&this->x, &this->y, &this->z, &this->w} {}
members(const T& x, const T& y, const T& z, const T& w) : m_values{&this->x, &this->y, &this->z, &this->w}, x(x), y(y), z(z), w(w) {}
members(const ::std::initializer_list<T> il) : m_values{&this->x, &this->y, &this->z, &this->w}, x(il.begin()[0]), y(il.begin()[1]), z(il.begin()[2]), w(il.begin()[3]) {
assert(il.size() == 4);
}
public:
T x;
T y;
T z;
T w;
};
template <typename T>
class members<T, ::std::numeric_limits<::std::size_t>::max()> {
protected:
constexpr static bool variable_sized = true;
constexpr static bool has_aliases = false;
::std::vector<T> m_values;
members() = default;
members(const ::std::size_t n) : m_values(n) {}
members(const ::std::size_t n, const T& value) : m_values(n, value) {}
template <typename InputIter>
members(const InputIter first, const InputIter last) : m_values(first, last) {}
members(const ::std::initializer_list<T> il) : m_values(il) {}
};
}
}
template <typename T, ::std::size_t N = ::std::numeric_limits<::std::size_t>::max()>
class vector : public ::tools::detail::vector::members<T, N> {
private:
using Base = ::tools::detail::vector::members<T, N>;
using F = ::std::conditional_t<::std::is_floating_point_v<T>, T, double>;
using V = ::tools::vector<T, N>;
constexpr static bool variable_sized = Base::variable_sized;
constexpr static bool has_aliases = Base::has_aliases;
public:
using reference = T&;
using const_reference = const T&;
using size_type = ::std::size_t;
using difference_type = ::std::ptrdiff_t;
using pointer = T*;
using const_pointer = const T*;
using value_type = T;
class iterator {
private:
V* m_parent;
size_type m_i;
public:
using difference_type = ::std::ptrdiff_t;
using value_type = T;
using reference = T&;
using pointer = T*;
using iterator_category = ::std::random_access_iterator_tag;
iterator() = default;
iterator(const iterator&) = default;
iterator(iterator&&) = default;
~iterator() = default;
iterator& operator=(const iterator&) = default;
iterator& operator=(iterator&&) = default;
iterator(V * const parent, const size_type i) : m_parent(parent), m_i(i) {}
reference operator*() const {
return (*this->m_parent)[this->m_i];
}
pointer operator->() const {
return &(*(*this));
}
iterator& operator++() {
++this->m_i;
return *this;
}
iterator operator++(int) {
const auto self = *this;
++*this;
return self;
}
iterator& operator--() {
--this->m_i;
return *this;
}
iterator operator--(int) {
const auto self = *this;
--*this;
return self;
}
iterator& operator+=(const difference_type n) {
this->m_i += n;
return *this;
}
iterator& operator-=(const difference_type n) {
this->m_i -= n;
return *this;
}
friend iterator operator+(const iterator& self, const difference_type n) {
return iterator(self) += n;
}
friend iterator operator+(const difference_type n, const iterator& self) {
return iterator(self) += n;
}
friend iterator operator-(const iterator& self, const difference_type n) {
return iterator(self) -= n;
}
friend difference_type operator-(const iterator& lhs, const iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return static_cast<difference_type>(lhs.m_i) - static_cast<difference_type>(rhs.m_i);
}
reference operator[](const difference_type n) const {
return *(*this + n);
}
friend bool operator==(const iterator& lhs, const iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return lhs.m_i == rhs.m_i;
}
friend bool operator!=(const iterator& lhs, const iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return lhs.m_i != rhs.m_i;
}
friend bool operator<(const iterator& lhs, const iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return lhs.m_i < rhs.m_i;
}
friend bool operator<=(const iterator& lhs, const iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return lhs.m_i <= rhs.m_i;
}
friend bool operator>(const iterator& lhs, const iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return lhs.m_i > rhs.m_i;
}
friend bool operator>=(const iterator& lhs, const iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return lhs.m_i >= rhs.m_i;
}
};
class const_iterator {
private:
const V *m_parent;
size_type m_i;
public:
using difference_type = ::std::ptrdiff_t;
using value_type = T;
using reference = const T&;
using pointer = const T*;
using iterator_category = ::std::random_access_iterator_tag;
const_iterator() = default;
const_iterator(const const_iterator&) = default;
const_iterator(const_iterator&&) = default;
~const_iterator() = default;
const_iterator& operator=(const const_iterator&) = default;
const_iterator& operator=(const_iterator&&) = default;
const_iterator(const V * const parent, const size_type i) : m_parent(parent), m_i(i) {}
reference operator*() const {
return (*this->m_parent)[this->m_i];
}
pointer operator->() const {
return &(*(*this));
}
const_iterator& operator++() {
++this->m_i;
return *this;
}
const_iterator operator++(int) {
const auto self = *this;
++*this;
return self;
}
const_iterator& operator--() {
--this->m_i;
return *this;
}
const_iterator operator--(int) {
const auto self = *this;
--*this;
return self;
}
const_iterator& operator+=(const difference_type n) {
this->m_i += n;
return *this;
}
const_iterator& operator-=(const difference_type n) {
this->m_i -= n;
return *this;
}
friend const_iterator operator+(const const_iterator& self, const difference_type n) {
return const_iterator(self) += n;
}
friend const_iterator operator+(const difference_type n, const const_iterator& self) {
return const_iterator(self) += n;
}
friend const_iterator operator-(const const_iterator& self, const difference_type n) {
return const_iterator(self) -= n;
}
friend difference_type operator-(const const_iterator& lhs, const const_iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return static_cast<difference_type>(lhs.m_i) - static_cast<difference_type>(rhs.m_i);
}
reference operator[](const difference_type n) const {
return *(*this + n);
}
friend bool operator==(const const_iterator& lhs, const const_iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return lhs.m_i == rhs.m_i;
}
friend bool operator!=(const const_iterator& lhs, const const_iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return lhs.m_i != rhs.m_i;
}
friend bool operator<(const const_iterator& lhs, const const_iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return lhs.m_i < rhs.m_i;
}
friend bool operator<=(const const_iterator& lhs, const const_iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return lhs.m_i <= rhs.m_i;
}
friend bool operator>(const const_iterator& lhs, const const_iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return lhs.m_i > rhs.m_i;
}
friend bool operator>=(const const_iterator& lhs, const const_iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return lhs.m_i >= rhs.m_i;
}
};
using reverse_iterator = ::std::reverse_iterator<iterator>;
using const_reverse_iterator = ::std::reverse_iterator<const_iterator>;
vector() = default;
vector(const V& other) : Base() {
if constexpr (has_aliases) {
::std::copy(other.begin(), other.end(), this->begin());
} else {
this->m_values = other.m_values;
}
}
vector(V&& other) noexcept {
if constexpr (has_aliases) {
::std::copy(other.begin(), other.end(), this->begin());
} else {
this->m_values = ::std::move(other.m_values);
}
}
~vector() = default;
V& operator=(const V& other) {
if constexpr (has_aliases) {
::std::copy(other.begin(), other.end(), this->begin());
} else {
this->m_values = other.m_values;
}
return *this;
}
V& operator=(V&& other) noexcept {
if constexpr (has_aliases) {
::std::copy(other.begin(), other.end(), this->begin());
} else {
this->m_values = ::std::move(other.m_values);
}
return *this;
}
template <bool SFINAE = variable_sized, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
explicit vector(size_type n) : Base(n) {}
template <bool SFINAE = variable_sized, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
vector(size_type n, const_reference value) : Base(n, value) {}
template <typename InputIter, bool SFINAE = variable_sized, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
vector(const InputIter first, const InputIter last) : Base(first, last) {}
template <bool SFINAE = N == 2, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
vector(const T& x, const T& y) : Base(x, y) {}
template <bool SFINAE = N == 3, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
vector(const T& x, const T& y, const T& z) : Base(x, y, z) {}
template <bool SFINAE = N == 4, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
vector(const T& x, const T& y, const T& z, const T& w) : Base(x, y, z, w) {}
vector(const ::std::initializer_list<T> il) : Base(il) {}
iterator begin() noexcept { return iterator(this, 0); }
const_iterator begin() const noexcept { return const_iterator(this, 0); }
const_iterator cbegin() const noexcept { return const_iterator(this, 0); }
iterator end() noexcept { return iterator(this, this->size()); }
const_iterator end() const noexcept { return const_iterator(this, this->size()); }
const_iterator cend() const noexcept { return const_iterator(this, this->size()); }
reverse_iterator rbegin() noexcept { return ::std::make_reverse_iterator(this->end()); }
const_reverse_iterator rbegin() const noexcept { return ::std::make_reverse_iterator(this->end()); }
const_reverse_iterator crbegin() const noexcept { return ::std::make_reverse_iterator(this->cend()); }
reverse_iterator rend() noexcept { return ::std::make_reverse_iterator(this->begin()); }
const_reverse_iterator rend() const noexcept { return ::std::make_reverse_iterator(this->begin()); }
const_reverse_iterator crend() const noexcept { return ::std::make_reverse_iterator(this->cbegin()); }
size_type size() const noexcept { return this->m_values.size(); }
bool empty() const noexcept { return this->m_values.empty(); }
reference operator[](const size_type n) {
if constexpr (has_aliases) {
return *this->m_values[n];
} else {
return this->m_values[n];
}
}
const_reference operator[](const size_type n) const {
if constexpr (has_aliases) {
return *this->m_values[n];
} else {
return this->m_values[n];
}
}
reference front() { return *this->begin(); }
const_reference front() const { return *this->begin(); }
reference back() { return *this->rbegin(); }
const_reference back() const { return *this->rbegin(); }
V operator+() const {
return *this;
}
V operator-() const {
V res = *this;
for (auto& v : res) v = -v;
return res;
}
V& operator+=(const V& other) {
assert(this->size() == other.size());
for (::std::size_t i = 0; i < this->size(); ++i) {
(*this)[i] += other[i];
}
return *this;
}
friend V operator+(const V& lhs, const V& rhs) {
return V(lhs) += rhs;
}
V& operator-=(const V& other) {
assert(this->size() == other.size());
for (::std::size_t i = 0; i < this->size(); ++i) {
(*this)[i] -= other[i];
}
return *this;
}
friend V operator-(const V& lhs, const V& rhs) {
return V(lhs) -= rhs;
}
V& operator*=(const T& c) {
for (auto& v : *this) v *= c;
return *this;
}
friend V operator*(const T& lhs, const V& rhs) {
return V(rhs) *= lhs;
}
friend V operator*(const V& lhs, const T& rhs) {
return V(lhs) *= rhs;
}
V& operator/=(const T& c) {
for (auto& v : *this) v /= c;
return *this;
}
friend V operator/(const V& lhs, const T& rhs) {
return V(lhs) /= rhs;
}
friend bool operator==(const V& lhs, const V& rhs) {
return ::std::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
}
friend bool operator!=(const V& lhs, const V& rhs) {
return !(lhs == rhs);
}
T inner_product(const V& other) const {
assert(this->size() == other.size());
T res{};
for (::std::size_t i = 0; i < this->size(); ++i) {
res += (*this)[i] * other[i];
}
return res;
}
T l1_norm() const {
T res{};
for (const auto& v : *this) {
res += ::tools::abs(v);
}
return res;
}
T squared_l2_norm() const {
return this->inner_product(*this);
}
F l2_norm() const {
return ::std::sqrt(static_cast<F>(this->squared_l2_norm()));
}
template <bool SFINAE = ::std::is_floating_point_v<T>, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
V normalized() const {
return *this / this->l2_norm();
}
friend ::std::ostream& operator<<(::std::ostream& os, const V& self) {
os << '(';
::std::string delimiter = "";
for (const auto& v : self) {
os << delimiter << v;
delimiter = ", ";
}
return os << ')';
}
friend ::std::istream& operator>>(::std::istream& is, V& self) {
for (auto& v : self) {
is >> v;
}
return is;
}
template <bool SFINAE = N == 2, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
T outer_product(const V& other) const {
return this->x * other.y - this->y * other.x;
}
template <bool SFINAE = N == 2, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
V turned90() const {
return V{-this->y, this->x};
}
template <bool SFINAE = N == 2, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
V turned270() const {
return V{this->y, -this->x};
}
template <bool SFINAE = N == 2, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
static const ::std::array<V, 4>& four_directions() {
static const ::std::array<V, 4> res = {
V{T(1), T(0)},
V{T(0), T(1)},
V{T(-1), T(0)},
V{T(0), T(-1)}
};
return res;
}
template <bool SFINAE = N == 2, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
static const ::std::array<V, 8>& eight_directions() {
static const ::std::array<V, 8> res = {
V{T(1), T(0)},
V{T(1), T(1)},
V{T(0), T(1)},
V{T(-1), T(1)},
V{T(-1), T(0)},
V{T(-1), T(-1)},
V{T(0), T(-1)},
V{T(1), T(-1)}
};
return res;
}
template <bool SFINAE = N == 3, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
V outer_product(const V& other) const {
return V{this->y * other.z - this->z * other.y, this->z * other.x - this->x * other.z, this->x * other.y - this->y * other.x};
}
template <bool SFINAE = N == 3 && ::std::is_floating_point_v<T>, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
::std::array<V, 3> orthonormal_basis() const {
assert((*this != V{0, 0, 0}));
::std::array<V, 3> v;
v[0] = *this;
v[1] = V{0, this->z, -this->y};
if (v[1] == V{0, 0, 0}) {
v[1] = V{-this->z, 0, this->x};
}
v[1] -= v[0].inner_product(v[1]) / v[0].inner_product(v[0]) * v[0];
v[0] = v[0].normalized();
v[1] = v[1].normalized();
v[2] = v[0].outer_product(v[1]);
return v;
}
};
}
namespace std {
template <typename T>
struct hash<::tools::vector<T, 2>> {
using result_type = ::std::size_t;
using argument_type = ::tools::vector<T, 2>;
result_type operator()(const argument_type& key) const {
static const ::tools::tuple_hash<T, T> hasher;
return hasher(::std::make_tuple(key.x, key.y));
}
};
template <typename T>
struct hash<::tools::vector<T, 3>> {
using result_type = ::std::size_t;
using argument_type = ::tools::vector<T, 3>;
result_type operator()(const argument_type& key) const {
static const ::tools::tuple_hash<T, T, T> hasher;
return hasher(::std::make_tuple(key.x, key.y, key.z));
}
};
template <typename T>
struct hash<::tools::vector<T, 4>> {
using result_type = ::std::size_t;
using argument_type = ::tools::vector<T, 4>;
result_type operator()(const argument_type& key) const {
static const ::tools::tuple_hash<T, T, T, T> hasher;
return hasher(::std::make_tuple(key.x, key.y, key.z, key.w));
}
};
}
#line 5 "tools/vector2.hpp"
namespace tools {
template <typename T>
using vector2 = ::tools::vector<T, 2>;
}
#line 23 "tools/detail/geometry_2d.hpp"
namespace tools {
template <typename T, bool Filled, bool HasRadius = true>
class circle_2d;
template <typename T>
class directed_line_segment_2d;
template <typename T>
class half_line_2d;
template <typename T>
class line_2d;
template <typename T, bool Filled>
class polygon_2d;
template <typename T, bool Filled>
class triangle_2d;
template <typename T, bool Filled, bool HasRadius>
class circle_2d {
::tools::vector2<T> m_center;
T m_radius;
T m_squared_radius;
public:
circle_2d() = default;
circle_2d(const ::tools::vector2<T>& center, const T& radius_or_squared_radius);
template <typename T_ = T, bool Filled_ = Filled>
::std::enable_if_t<::std::is_floating_point_v<T_> && Filled_, T> area() const;
::tools::vector2<T> center() const;
template <bool HasRadius_ = HasRadius>
::std::enable_if_t<HasRadius_, T> radius() const;
T squared_radius() const;
::std::pair<int, int> where(const ::tools::circle_2d<T, Filled, HasRadius>& other) const;
int where(const ::tools::vector2<T>& p) const;
template <typename T_, bool HasRadius_>
friend ::std::enable_if_t<::std::is_floating_point_v<T_>, ::std::optional<::std::variant<::tools::circle_2d<T_, false, HasRadius_>, ::std::vector<::tools::vector2<T_>>>>>
operator&(const ::tools::circle_2d<T_, false, HasRadius_>& lhs, const ::tools::circle_2d<T_, false, HasRadius_>& rhs);
template <typename T_, bool HasRadius_>
friend ::std::enable_if_t<::std::is_floating_point_v<T_>, ::std::vector<::tools::vector2<T_>>>
operator&(const ::tools::circle_2d<T_, false, HasRadius_>& lhs, const ::tools::line_2d<T_>& rhs);
template <typename T_, bool HasRadius_>
friend ::std::enable_if_t<::std::is_floating_point_v<T_>, ::std::optional<::std::variant<::tools::vector2<T_>, ::tools::directed_line_segment_2d<T_>>>>
operator&(const ::tools::circle_2d<T_, true, HasRadius_>& lhs, const ::tools::line_2d<T_>& rhs);
template <typename T_, bool Filled_, bool HasRadius1, bool HasRadius2>
friend bool operator==(const ::tools::circle_2d<T_, Filled_, HasRadius1>& lhs, const ::tools::circle_2d<T_, Filled_, HasRadius2>& rhs);
template <typename T_, bool Filled_, bool HasRadius1, bool HasRadius2>
friend bool operator!=(const ::tools::circle_2d<T_, Filled_, HasRadius1>& lhs, const ::tools::circle_2d<T_, Filled_, HasRadius2>& rhs);
};
template <typename T>
class directed_line_segment_2d {
::tools::vector2<T> m_p1;
::tools::vector2<T> m_p2;
public:
directed_line_segment_2d() = default;
directed_line_segment_2d(const ::tools::vector2<T>& p1, const ::tools::vector2<T>& p2);
bool contains(const ::tools::vector2<T>& p) const;
::std::conditional_t<::std::is_floating_point_v<T>, T, double> length() const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
cross_point(const ::tools::directed_line_segment_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
cross_point(const ::tools::half_line_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
cross_point(const ::tools::line_2d<T>& other) const;
bool crosses(const ::tools::directed_line_segment_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::tools::vector2<T>>
midpoint() const;
const ::tools::vector2<T>& p1() const;
const ::tools::vector2<T>& p2() const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
squared_distance(const ::tools::directed_line_segment_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
squared_distance(const ::tools::half_line_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
squared_distance(const ::tools::line_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
squared_distance(const ::tools::vector2<T>& p) const;
T squared_length() const;
::tools::half_line_2d<T> to_half_line() const;
::tools::line_2d<T> to_line() const;
::tools::vector2<T> to_vector() const;
::tools::directed_line_segment_2d<T> operator+() const;
::tools::directed_line_segment_2d<T> operator-() const;
template <typename T_>
friend ::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::std::variant<::tools::vector2<T_>, ::tools::directed_line_segment_2d<T_>>>>
operator&(const ::tools::directed_line_segment_2d<T_>& lhs, const ::tools::directed_line_segment_2d<T_>& rhs);
template <typename T_>
friend ::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::std::variant<::tools::vector2<T_>, ::tools::directed_line_segment_2d<T_>>>>
operator&(const ::tools::directed_line_segment_2d<T_>& lhs, const ::tools::half_line_2d<T_>& rhs);
template <typename T_>
friend ::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::std::variant<::tools::vector2<T_>, ::tools::directed_line_segment_2d<T_>>>>
operator&(const ::tools::directed_line_segment_2d<T_>& lhs, const ::tools::line_2d<T_>& rhs);
template <typename T_>
friend bool operator==(const ::tools::directed_line_segment_2d<T_>& lhs, const ::tools::directed_line_segment_2d<T_>& rhs);
template <typename T_>
friend bool operator!=(const ::tools::directed_line_segment_2d<T_>& lhs, const ::tools::directed_line_segment_2d<T_>& rhs);
};
template <typename T>
class half_line_2d {
::tools::vector2<T> m_a;
::tools::vector2<T> m_d;
public:
half_line_2d() = default;
half_line_2d(const ::tools::vector2<T>& a, const ::tools::vector2<T>& d);
const ::tools::vector2<T>& a() const;
bool contains(const ::tools::vector2<T>& p) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
cross_point(const ::tools::directed_line_segment_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
cross_point(const ::tools::half_line_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
cross_point(const ::tools::line_2d<T>& other) const;
const ::tools::vector2<T>& d() const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
squared_distance(const ::tools::directed_line_segment_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
squared_distance(const ::tools::half_line_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
squared_distance(const ::tools::line_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
squared_distance(const ::tools::vector2<T>& p) const;
::tools::line_2d<T> to_line() const;
template <typename T_>
friend ::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::std::variant<::tools::vector2<T_>, ::tools::directed_line_segment_2d<T_>>>>
operator&(const ::tools::half_line_2d<T_>& lhs, const ::tools::directed_line_segment_2d<T_>& rhs);
template <typename T_>
friend ::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::std::variant<::tools::vector2<T_>, ::tools::directed_line_segment_2d<T_>, ::tools::half_line_2d<T_>>>>
operator&(const ::tools::half_line_2d<T_>& lhs, const ::tools::half_line_2d<T_>& rhs);
template <typename T_>
friend ::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::std::variant<::tools::vector2<T_>, ::tools::half_line_2d<T_>>>>
operator&(const ::tools::half_line_2d<T_>& lhs, const ::tools::line_2d<T_>& rhs);
template <typename T_>
friend bool operator==(const ::tools::half_line_2d<T_>& lhs, const ::tools::half_line_2d<T_>& rhs);
template <typename T_>
friend bool operator!=(const ::tools::half_line_2d<T_>& lhs, const ::tools::half_line_2d<T_>& rhs);
};
template <typename T>
class line_2d {
T m_a;
T m_b;
T m_c;
public:
line_2d() = default;
line_2d(const T& a, const T& b, const T& c);
const T& a() const;
const T& b() const;
const T& c() const;
bool contains(const ::tools::vector2<T>& p) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
cross_point(const ::tools::directed_line_segment_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
cross_point(const ::tools::half_line_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
cross_point(const ::tools::line_2d<T>& other) const;
bool crosses(const ::tools::line_2d<T>& other) const;
bool is_parallel_to(const ::tools::line_2d<T>& other) const;
::tools::vector2<T> normal() const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::tools::vector2<T>>
projection(const ::tools::vector2<T>& p) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
squared_distance(const ::tools::directed_line_segment_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
squared_distance(const ::tools::half_line_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
squared_distance(const ::tools::line_2d<T>& other) const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
squared_distance(const ::tools::vector2<T>& p) const;
template <typename T_, bool HasRadius_>
friend ::std::enable_if_t<::std::is_floating_point_v<T_>, ::std::vector<::tools::vector2<T_>>>
operator&(const ::tools::line_2d<T_>& lhs, const ::tools::circle_2d<T_, false, HasRadius_>& rhs);
template <typename T_, bool HasRadius_>
friend ::std::enable_if_t<::std::is_floating_point_v<T_>, ::std::optional<::std::variant<::tools::vector2<T_>, ::tools::directed_line_segment_2d<T_>>>>
operator&(const ::tools::line_2d<T_>& lhs, const ::tools::circle_2d<T_, true, HasRadius_>& rhs);
template <typename T_>
friend ::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::std::variant<::tools::vector2<T_>, ::tools::directed_line_segment_2d<T_>>>>
operator&(const ::tools::line_2d<T_>& lhs, const ::tools::directed_line_segment_2d<T_>& rhs);
template <typename T_>
friend ::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::std::variant<::tools::vector2<T_>, ::tools::half_line_2d<T_>>>>
operator&(const ::tools::line_2d<T_>& lhs, const ::tools::half_line_2d<T_>& rhs);
template <typename T_>
friend ::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::std::variant<::tools::vector2<T_>, ::tools::line_2d<T_>>>>
operator&(const ::tools::line_2d<T_>& lhs, const ::tools::line_2d<T_>& rhs);
template <typename T_>
friend bool operator==(const ::tools::line_2d<T_>& lhs, const ::tools::line_2d<T_>& rhs);
template <typename T_>
friend bool operator!=(const ::tools::line_2d<T_>& lhs, const ::tools::line_2d<T_>& rhs);
static ::tools::line_2d<T> through(const ::tools::vector2<T>& p1, const ::tools::vector2<T>& p2);
};
template <typename T, bool Filled>
class polygon_2d {
protected:
::std::vector<::tools::vector2<T>> m_points;
T doubled_signed_area() const;
public:
polygon_2d() = default;
template <typename InputIterator>
polygon_2d(const InputIterator& begin, const InputIterator& end);
polygon_2d(::std::initializer_list<::tools::vector2<T>> init);
template <typename T_ = T, bool Filled_ = Filled>
::std::enable_if_t<(::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>) && Filled_, T> area() const;
template <bool Filled_ = Filled>
::std::enable_if_t<Filled_, T> doubled_area() const;
bool is_counterclockwise() const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::tools::circle_2d<T, Filled, false>> minimum_bounding_circle() const;
int where(const ::tools::vector2<T>& p) const;
};
template <typename T, bool Filled>
class triangle_2d : public polygon_2d<T, Filled> {
template <typename OutputIterator>
void sorted_edges(OutputIterator result) const;
public:
triangle_2d() = default;
template <typename InputIterator>
triangle_2d(const InputIterator& begin, const InputIterator& end);
triangle_2d(::std::initializer_list<::tools::vector2<T>> init);
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::tools::circle_2d<T, Filled, false>> circumcircle() const;
template <typename T_ = T>
::std::enable_if_t<::std::is_floating_point_v<T_>, ::tools::circle_2d<T, Filled>> incircle() const;
template <typename T_ = T>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::tools::circle_2d<T, Filled, false>> minimum_bounding_circle() const;
int type() const;
};
template <typename T, bool Filled, bool HasRadius>
circle_2d<T, Filled, HasRadius>::circle_2d(const ::tools::vector2<T>& center, const T& radius_or_squared_radius) : m_center(center) {
assert(radius_or_squared_radius > T(0));
if constexpr (HasRadius) {
this->m_radius = radius_or_squared_radius;
this->m_squared_radius = ::tools::square(this->m_radius);
} else {
this->m_squared_radius = radius_or_squared_radius;
}
}
template <typename T, bool Filled, bool HasRadius> template <typename T_, bool Filled_>
::std::enable_if_t<::std::is_floating_point_v<T_> && Filled_, T> circle_2d<T, Filled, HasRadius>::area() const {
return ::std::acos(T(-1)) * this->m_squared_radius;
}
template <typename T, bool Filled, bool HasRadius>
::tools::vector2<T> circle_2d<T, Filled, HasRadius>::center() const {
return this->m_center;
}
template <typename T, bool Filled, bool HasRadius> template <bool HasRadius_>
::std::enable_if_t<HasRadius_, T> circle_2d<T, Filled, HasRadius>::radius() const {
return this->m_radius;
}
template <typename T, bool Filled, bool HasRadius>
T circle_2d<T, Filled, HasRadius>::squared_radius() const {
return this->m_squared_radius;
}
template <typename T, bool Filled, bool HasRadius>
::std::pair<int, int> circle_2d<T, Filled, HasRadius>::where(const ::tools::circle_2d<T, Filled, HasRadius>& other) const {
return ::std::make_pair([&]() {
if (*this == other) {
return ::std::numeric_limits<int>::max();
}
if constexpr (HasRadius) {
const auto d2 = (this->m_center - other.m_center).squared_l2_norm();
const auto& a_r = this->m_radius;
const auto& b_r = other.m_radius;
const ::std::array<T, 2> threshold = {::tools::square(a_r - b_r), ::tools::square(a_r + b_r)};
if (d2 < threshold[0]) {
return 0;
} else if (d2 == threshold[0]) {
return 1;
} else if (d2 == threshold[1]) {
return 3;
} else if (threshold[1] < d2) {
return 4;
} else {
return 2;
}
} else {
const auto d2 = (this->m_center - other.m_center).squared_l2_norm();
const auto& a_r2 = this->m_squared_radius;
const auto& b_r2 = other.m_squared_radius;
const auto threshold = a_r2 + b_r2 - d2;
const auto squared_threshold = ::tools::square(threshold);
const auto v = T(4) * a_r2 * b_r2;
if (threshold > T(0) && v < squared_threshold) {
return 0;
} else if (threshold > T(0) && v == squared_threshold) {
return 1;
} else if (threshold < T(0) && v == squared_threshold) {
return 3;
} else if (threshold < T(0) && v < squared_threshold) {
return 4;
} else {
return 2;
}
}
}(), ::tools::signum(this->m_squared_radius - other.m_squared_radius));
}
template <typename T, bool Filled, bool HasRadius>
int circle_2d<T, Filled, HasRadius>::where(const ::tools::vector2<T>& p) const {
return ::tools::signum(this->m_squared_radius - (p - this->m_center).squared_l2_norm());
}
template <typename T, bool HasRadius>
::std::enable_if_t<::std::is_floating_point_v<T>, ::std::optional<::std::variant<::tools::circle_2d<T, false, HasRadius>, ::std::vector<::tools::vector2<T>>>>>
operator&(const ::tools::circle_2d<T, false, HasRadius>& lhs, const ::tools::circle_2d<T, false, HasRadius>& rhs) {
using variant_t = ::std::variant<::tools::circle_2d<T, false, HasRadius>, ::std::vector<::tools::vector2<T>>>;
using result_t = ::std::optional<variant_t>;
const auto t = lhs.where(rhs).first;
if (t == ::std::numeric_limits<int>::max()) return result_t(variant_t(lhs));
if (t == 0 || t == 4) return ::std::nullopt;
const auto& x1 = lhs.m_center.x;
const auto& y1 = lhs.m_center.y;
const auto& x2 = rhs.m_center.x;
const auto& y2 = rhs.m_center.y;
const ::tools::line_2d<T> l(2 * (x2 - x1), 2 * (y2 - y1), (x1 + x2) * (x1 - x2) + (y1 + y2) * (y1 - y2) + rhs.m_squared_radius - lhs.m_squared_radius);
return result_t(variant_t(lhs & l));
}
template <typename T, bool HasRadius>
::std::enable_if_t<::std::is_floating_point_v<T>, ::std::vector<::tools::vector2<T>>>
operator&(const ::tools::circle_2d<T, false, HasRadius>& lhs, const ::tools::line_2d<T>& rhs) {
using result_t = ::std::vector<::tools::vector2<T>>;
if (const auto intersection = ::tools::circle_2d<T, true, HasRadius>(lhs.m_center, HasRadius ? lhs.m_radius : lhs.m_squared_radius) & rhs; intersection) {
struct {
result_t operator()(const ::tools::vector2<T>& v) {
return result_t({v});
}
result_t operator()(const ::tools::directed_line_segment_2d<T>& s) {
return result_t({s.p1(), s.p2()});
}
} visitor;
return ::std::visit(visitor, *intersection);
} else {
return result_t();
}
}
template <typename T, bool HasRadius>
::std::enable_if_t<::std::is_floating_point_v<T>, ::std::optional<::std::variant<::tools::vector2<T>, ::tools::directed_line_segment_2d<T>>>>
operator&(const ::tools::circle_2d<T, true, HasRadius>& lhs, const ::tools::line_2d<T>& rhs) {
using variant_t = ::std::variant<::tools::vector2<T>, ::tools::directed_line_segment_2d<T>>;
using result_t = ::std::optional<variant_t>;
const auto [a, b, c] = (rhs.projection(lhs.m_center) - lhs.m_center).inner_product(rhs.normal()) >= T(0) ? ::std::make_tuple(rhs.a(), rhs.b(), rhs.c()) : ::std::make_tuple(-rhs.a(), -rhs.b(), -rhs.c());
const auto& x = lhs.m_center.x;
const auto& y = lhs.m_center.y;
const auto r = HasRadius ? lhs.m_radius : ::std::sqrt(lhs.m_squared_radius);
const auto& r2 = lhs.m_squared_radius;
const auto d2 = rhs.squared_distance(lhs.m_center);
if (d2 < r2) {
const auto D = ::std::abs(a * x + b * y + c);
return result_t(variant_t(::tools::directed_line_segment_2d<T>(
::tools::vector2<T>((a * D - b * ::std::sqrt((a * a + b * b) * r2 - D * D)) / (a * a + b * b) + x, (b * D + a * ::std::sqrt((a * a + b * b) * r2 - D * D)) / (a * a + b * b) + y),
::tools::vector2<T>((a * D + b * ::std::sqrt((a * a + b * b) * r2 - D * D)) / (a * a + b * b) + x, (b * D - a * ::std::sqrt((a * a + b * b) * r2 - D * D)) / (a * a + b * b) + y)
)));
} else if (d2 == r2) {
return result_t(variant_t(::tools::vector2<T>(a * r / ::std::sqrt(a * a + b * b) + x, b * r / ::std::sqrt(a * a + b * b) + y)));
} else {
return ::std::nullopt;
}
}
template <typename T, bool Filled, bool HasRadius1, bool HasRadius2>
bool operator==(const ::tools::circle_2d<T, Filled, HasRadius1>& lhs, const ::tools::circle_2d<T, Filled, HasRadius2>& rhs) {
return lhs.m_center == rhs.m_center && lhs.m_squared_radius == rhs.m_squared_radius;
}
template <typename T, bool Filled, bool HasRadius1, bool HasRadius2>
bool operator!=(const ::tools::circle_2d<T, Filled, HasRadius1>& lhs, const ::tools::circle_2d<T, Filled, HasRadius2>& rhs) {
return !(lhs == rhs);
}
template <typename T>
directed_line_segment_2d<T>::directed_line_segment_2d(const ::tools::vector2<T>& p1, const ::tools::vector2<T>& p2) :
m_p1(p1),
m_p2(p2) {
assert(p1 != p2);
}
template <typename T>
bool directed_line_segment_2d<T>::contains(const ::tools::vector2<T>& p) const {
if (p == this->m_p1 || p == this->m_p2) return true;
const ::tools::line_2d<T> l = this->to_line();
if (!l.contains(p)) return false;
const T d = (p - this->m_p1).inner_product(this->to_vector());
return T(0) <= d && d <= this->squared_length();
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
directed_line_segment_2d<T>::cross_point(const ::tools::directed_line_segment_2d<T>& other) const {
using result_t = ::std::optional<::tools::vector2<T>>;
const auto intersection = *this & other;
struct {
result_t operator()(const ::tools::vector2<T>& v) {
return result_t(v);
}
result_t operator()(const ::tools::directed_line_segment_2d<T>&) {
return ::std::nullopt;
}
} visitor;
return intersection ? ::std::visit(visitor, *intersection) : ::std::nullopt;
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
directed_line_segment_2d<T>::cross_point(const ::tools::half_line_2d<T>& other) const {
using result_t = ::std::optional<::tools::vector2<T>>;
const auto intersection = *this & other;
struct {
result_t operator()(const ::tools::vector2<T>& v) {
return result_t(v);
}
result_t operator()(const ::tools::directed_line_segment_2d<T>&) {
return ::std::nullopt;
}
} visitor;
return intersection ? ::std::visit(visitor, *intersection) : ::std::nullopt;
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
directed_line_segment_2d<T>::cross_point(const ::tools::line_2d<T>& other) const {
using result_t = ::std::optional<::tools::vector2<T>>;
const auto intersection = *this & other;
struct {
result_t operator()(const ::tools::vector2<T>& v) {
return result_t(v);
}
result_t operator()(const ::tools::directed_line_segment_2d<T>&) {
return result_t();
}
} visitor;
return intersection ? ::std::visit(visitor, *intersection) : ::std::nullopt;
}
template <typename T>
bool directed_line_segment_2d<T>::crosses(const ::tools::directed_line_segment_2d<T>& other) const {
if (this->to_line() == other.to_line()) {
const auto base = this->to_vector();
const auto fixed_other = base.inner_product(other.to_vector()) > T(0) ? other : -other;
const T d1(0);
const T d2 = base.inner_product(base);
const T d3 = base.inner_product(fixed_other.m_p1 - this->m_p1);
const T d4 = base.inner_product(fixed_other.m_p2 - this->m_p1);
return d1 == d4 || d2 == d3;
}
return ::tools::signum(this->to_vector().outer_product(other.m_p1 - this->m_p1)) * ::tools::signum(this->to_vector().outer_product(other.m_p2 - this->m_p1)) <= 0
&& ::tools::signum(other.to_vector().outer_product(this->m_p1 - other.m_p1)) * ::tools::signum(other.to_vector().outer_product(this->m_p2 - other.m_p1)) <= 0;
}
template <typename T>
::std::conditional_t<::std::is_floating_point_v<T>, T, double> directed_line_segment_2d<T>::length() const {
return this->to_vector().l2_norm();
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::tools::vector2<T>>
directed_line_segment_2d<T>::midpoint() const {
return (this->m_p1 + this->m_p2) / T(2);
}
template <typename T>
const ::tools::vector2<T>& directed_line_segment_2d<T>::p1() const {
return this->m_p1;
}
template <typename T>
const ::tools::vector2<T>& directed_line_segment_2d<T>::p2() const {
return this->m_p2;
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
directed_line_segment_2d<T>::squared_distance(const ::tools::directed_line_segment_2d<T>& other) const {
if (*this & other) {
return T(0);
}
return ::std::min({
other.squared_distance(this->m_p1),
other.squared_distance(this->m_p2),
this->squared_distance(other.m_p1),
this->squared_distance(other.m_p2)
});
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
directed_line_segment_2d<T>::squared_distance(const ::tools::half_line_2d<T>& other) const {
if (*this & other) {
return T(0);
}
return ::std::min({
other.squared_distance(this->m_p1),
other.squared_distance(this->m_p2)
});
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
directed_line_segment_2d<T>::squared_distance(const ::tools::line_2d<T>& other) const {
if (*this & other) {
return T(0);
}
return ::std::min({
other.squared_distance(this->m_p1),
other.squared_distance(this->m_p2)
});
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
directed_line_segment_2d<T>::squared_distance(const ::tools::vector2<T>& p) const {
const auto x = this->to_line().projection(p);
const auto d = this->to_vector().inner_product(x - this->m_p1);
return (p - (d < T(0) ? this->m_p1 : this->squared_length() < d ? this->m_p2 : x)).squared_l2_norm();
}
template <typename T>
T directed_line_segment_2d<T>::squared_length() const {
return this->to_vector().squared_l2_norm();
}
template <typename T>
::tools::half_line_2d<T> directed_line_segment_2d<T>::to_half_line() const {
return ::tools::half_line_2d<T>(this->m_p1, this->m_p2 - this->m_p1);
}
template <typename T>
::tools::line_2d<T> directed_line_segment_2d<T>::to_line() const {
return ::tools::line_2d<T>::through(this->m_p1, this->m_p2);
}
template <typename T>
::tools::vector2<T> directed_line_segment_2d<T>::to_vector() const {
return this->m_p2 - this->m_p1;
}
template <typename T>
::tools::directed_line_segment_2d<T> directed_line_segment_2d<T>::operator+() const {
return *this;
}
template <typename T>
::tools::directed_line_segment_2d<T> directed_line_segment_2d<T>::operator-() const {
return ::tools::directed_line_segment_2d<T>(this->m_p2, this->m_p1);
}
template <typename T>
::std::enable_if_t<::tools::is_rational_v<T> || ::std::is_floating_point_v<T>, ::std::optional<::std::variant<::tools::vector2<T>, ::tools::directed_line_segment_2d<T>>>>
operator&(const ::tools::directed_line_segment_2d<T>& lhs, const ::tools::directed_line_segment_2d<T>& rhs) {
using variant_t = ::std::variant<::tools::vector2<T>, ::tools::directed_line_segment_2d<T>>;
using result_t = ::std::optional<variant_t>;
const ::tools::line_2d<T> l1 = lhs.to_line();
const ::tools::line_2d<T> l2 = rhs.to_line();
if (l1 == l2) {
const ::tools::vector2<T> base = lhs.to_vector();
const ::tools::directed_line_segment_2d<T> fixed_rhs = base.inner_product(rhs.to_vector()) > T(0) ? rhs : -rhs;
const T d1(0);
const T d2 = base.inner_product(base);
const T d3 = base.inner_product(fixed_rhs.m_p1 - lhs.m_p1);
const T d4 = base.inner_product(fixed_rhs.m_p2 - lhs.m_p1);
if (d1 == d4) return result_t(variant_t(lhs.m_p1));
if (d2 == d3) return result_t(variant_t(lhs.m_p2));
if (d3 <= d1 && d2 <= d4) return result_t(variant_t(lhs));
if (d1 <= d3 && d4 <= d2) return result_t(variant_t(fixed_rhs));
if (d3 <= d1 && d1 <= d4 && d4 <= d2) return result_t(variant_t(::tools::directed_line_segment_2d<T>(lhs.m_p1, fixed_rhs.m_p2)));
if (d1 <= d3 && d3 <= d2 && d2 <= d4) return result_t(variant_t(::tools::directed_line_segment_2d<T>(fixed_rhs.m_p1, lhs.m_p2)));
return ::std::nullopt;
}
if (l1.is_parallel_to(l2)) return ::std::nullopt;
if (lhs.m_p1 == rhs.m_p1 || lhs.m_p1 == rhs.m_p2) return result_t(variant_t(lhs.m_p1));
if (lhs.m_p2 == rhs.m_p1 || lhs.m_p2 == rhs.m_p2) return result_t(variant_t(lhs.m_p2));
if (
::tools::signum(lhs.to_vector().outer_product(rhs.m_p1 - lhs.m_p1)) * ::tools::signum(lhs.to_vector().outer_product(rhs.m_p2 - lhs.m_p1)) > 0
|| ::tools::signum(rhs.to_vector().outer_product(lhs.m_p1 - rhs.m_p1)) * ::tools::signum(rhs.to_vector().outer_product(lhs.m_p2 - rhs.m_p1)) > 0
) return ::std::nullopt;
return result_t(variant_t(*l1.cross_point(l2)));
}
template <typename T>
::std::enable_if_t<::tools::is_rational_v<T> || ::std::is_floating_point_v<T>, ::std::optional<::std::variant<::tools::vector2<T>, ::tools::directed_line_segment_2d<T>>>>
operator&(const ::tools::directed_line_segment_2d<T>& lhs, const ::tools::half_line_2d<T>& rhs) {
using variant_t = ::std::variant<::tools::vector2<T>, ::tools::directed_line_segment_2d<T>>;
using result_t = ::std::optional<variant_t>;
const ::tools::line_2d<T> l1 = lhs.to_line();
const ::tools::line_2d<T> l2 = rhs.to_line();
if (l1 == l2) {
const bool has_same_direction = rhs.d().inner_product(lhs.to_vector()) > T(0);
const T d1 = rhs.d().inner_product(lhs.m_p1 - rhs.a());
const T d2 = rhs.d().inner_product(lhs.m_p2 - rhs.a());
if (has_same_direction) {
if (d2 < T(0)) return ::std::nullopt;
if (d2 == T(0)) return result_t(variant_t(rhs.a()));
if (d1 < T(0)) return result_t(variant_t(::tools::directed_line_segment_2d<T>(rhs.a(), lhs.m_p2)));
return result_t(variant_t(lhs));
} else {
if (d1 > T(0)) return ::std::nullopt;
if (d1 == T(0)) return result_t(variant_t(rhs.a()));
if (d2 > T(0)) return result_t(variant_t(::tools::directed_line_segment_2d<T>(lhs.m_p1, rhs.a())));
return result_t(variant_t(lhs));
}
}
if (rhs.contains(lhs.m_p1)) return result_t(variant_t(lhs.m_p1));
if (rhs.contains(lhs.m_p2)) return result_t(variant_t(lhs.m_p2));
if ((l2.a() * lhs.m_p1.x + l2.b() * lhs.m_p1.y + l2.c()) * (l2.a() * lhs.m_p2.x + l2.b() * lhs.m_p2.y + l2.c()) > T(0)) return ::std::nullopt;
const ::tools::vector2<T> possible_cross_point = *l1.cross_point(l2);
if (rhs.d().inner_product(possible_cross_point - rhs.a()) < T(0)) return ::std::nullopt;
return result_t(variant_t(possible_cross_point));
}
template <typename T>
::std::enable_if_t<::tools::is_rational_v<T> || ::std::is_floating_point_v<T>, ::std::optional<::std::variant<::tools::vector2<T>, ::tools::directed_line_segment_2d<T>>>>
operator&(const ::tools::directed_line_segment_2d<T>& lhs, const ::tools::line_2d<T>& rhs) {
using variant_t = ::std::variant<::tools::vector2<T>, ::tools::directed_line_segment_2d<T>>;
using result_t = ::std::optional<variant_t>;
const ::tools::line_2d<T> lhs_line = lhs.to_line();
if (lhs_line == rhs) return result_t(variant_t(lhs));
if (rhs.contains(lhs.m_p1)) return result_t(variant_t(lhs.m_p1));
if (rhs.contains(lhs.m_p2)) return result_t(variant_t(lhs.m_p2));
if ((rhs.a() * lhs.m_p1.x + rhs.b() * lhs.m_p1.y + rhs.c()) * (rhs.a() * lhs.m_p2.x + rhs.b() * lhs.m_p2.y + rhs.c()) > T(0)) return ::std::nullopt;
return result_t(variant_t(*lhs_line.cross_point(rhs)));
}
template <typename T>
bool operator==(const ::tools::directed_line_segment_2d<T>& lhs, const ::tools::directed_line_segment_2d<T>& rhs) {
return lhs.p1() == rhs.p1() && lhs.p2() == rhs.p2();
}
template <typename T>
bool operator!=(const ::tools::directed_line_segment_2d<T>& lhs, const ::tools::directed_line_segment_2d<T>& rhs) {
return !(lhs == rhs);
}
template <typename T>
half_line_2d<T>::half_line_2d(const ::tools::vector2<T>& a, const ::tools::vector2<T>& d) :
m_a(a),
m_d(d) {
assert(d != ::tools::vector2<T>(T(0), T(0)));
}
template <typename T>
const ::tools::vector2<T>& half_line_2d<T>::a() const {
return this->m_a;
}
template <typename T>
bool half_line_2d<T>::contains(const ::tools::vector2<T>& p) const {
const ::tools::line_2d<T> l = this->to_line();
return l.a() * p.x + l.b() * p.y + l.c() == T(0) && this->m_d.inner_product(p - this->m_a) >= T(0);
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
half_line_2d<T>::cross_point(const ::tools::directed_line_segment_2d<T>& other) const {
return other.cross_point(*this);
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
half_line_2d<T>::cross_point(const ::tools::half_line_2d<T>& other) const {
using result_t = ::std::optional<::tools::vector2<T>>;
const auto intersection = *this & other;
struct {
result_t operator()(const ::tools::vector2<T>& v) {
return result_t(v);
}
result_t operator()(const ::tools::directed_line_segment_2d<T>&) {
return ::std::nullopt;
}
result_t operator()(const ::tools::half_line_2d<T>&) {
return ::std::nullopt;
}
} visitor;
return intersection ? ::std::visit(visitor, *intersection) : ::std::nullopt;
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
half_line_2d<T>::cross_point(const ::tools::line_2d<T>& other) const {
using result_t = ::std::optional<::tools::vector2<T>>;
const auto intersection = *this & other;
struct {
result_t operator()(const ::tools::vector2<T>& v) {
return result_t(v);
}
result_t operator()(const ::tools::half_line_2d<T>&) {
return ::std::nullopt;
}
} visitor;
return intersection ? ::std::visit(visitor, *intersection) : ::std::nullopt;
}
template <typename T>
const ::tools::vector2<T>& half_line_2d<T>::d() const {
return this->m_d;
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
half_line_2d<T>::squared_distance(const ::tools::directed_line_segment_2d<T>& other) const {
return other.squared_distance(*this);
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
half_line_2d<T>::squared_distance(const ::tools::half_line_2d<T>& other) const {
if (*this & other) {
return T(0);
}
if (const auto x = this->to_line().cross_point(other.to_line()); x) {
if (this->m_d.inner_product(*x - this->m_a) >= T(0)) {
return (other.m_a - *x).squared_l2_norm();
} else if (other.m_d.inner_product(*x - other.m_a) >= T(0)) {
return (this->m_a - *x).squared_l2_norm();
} else {
return (this->m_a - other.m_a).squared_l2_norm();
}
} else {
if (this->m_d.inner_product(other.m_a) > T(0)) {
return this->to_line().squared_distance(other.to_line());
} else if (const auto x = this->to_line().projection(other.m_a); this->m_d.inner_product(x - this->m_a) >= T(0)) {
return this->to_line().squared_distance(other.to_line());
} else {
return (this->m_a - other.m_a).squared_l2_norm();
}
}
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
half_line_2d<T>::squared_distance(const ::tools::line_2d<T>& other) const {
if (*this & other) {
return T(0);
}
return other.squared_distance(this->m_a);
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
half_line_2d<T>::squared_distance(const ::tools::vector2<T>& p) const {
auto x = this->to_line().projection(p);
const auto d = this->m_d.inner_product(x - this->m_a);
return (p - (d < T(0) ? this->m_a : x)).squared_l2_norm();
}
template <typename T>
::tools::line_2d<T> half_line_2d<T>::to_line() const {
return ::tools::line_2d<T>::through(this->m_a, this->m_a + this->m_d);
}
template <typename T>
::std::enable_if_t<::tools::is_rational_v<T> || ::std::is_floating_point_v<T>, ::std::optional<::std::variant<::tools::vector2<T>, ::tools::directed_line_segment_2d<T>>>>
operator&(const ::tools::half_line_2d<T>& lhs, const ::tools::directed_line_segment_2d<T>& rhs) {
return rhs & lhs;
}
template <typename T>
::std::enable_if_t<::tools::is_rational_v<T> || ::std::is_floating_point_v<T>, ::std::optional<::std::variant<::tools::vector2<T>, ::tools::directed_line_segment_2d<T>, ::tools::half_line_2d<T>>>>
operator&(const ::tools::half_line_2d<T>& lhs, const ::tools::half_line_2d<T>& rhs) {
using variant_t = ::std::variant<::tools::vector2<T>, ::tools::directed_line_segment_2d<T>, ::tools::half_line_2d<T>>;
using result_t = ::std::optional<variant_t>;
const ::tools::line_2d<T> l1 = lhs.to_line();
const ::tools::line_2d<T> l2 = rhs.to_line();
if (l1 == l2) {
if (lhs.d().inner_product(rhs.d()) > T(0)) {
switch (::tools::signum(lhs.d().inner_product(rhs.a() - lhs.a()))) {
case 1:
case 0:
return result_t(variant_t(rhs));
default:
return result_t(variant_t(lhs));
}
} else {
switch (::tools::signum(lhs.d().inner_product(rhs.a() - lhs.a()))) {
case 1:
return result_t(variant_t(::tools::directed_line_segment_2d<T>(lhs.a(), rhs.a())));
case 0:
return result_t(variant_t(lhs.a()));
default:
return ::std::nullopt;
}
}
} else if (l1.is_parallel_to(l2)) {
return ::std::nullopt;
} else {
const ::tools::vector2<T> possible_cross_point = *l1.cross_point(l2);
if (lhs.d().inner_product(possible_cross_point - lhs.a()) < T(0) || rhs.d().inner_product(possible_cross_point - rhs.a()) < T(0)) {
return ::std::nullopt;
}
return result_t(variant_t(possible_cross_point));
}
}
template <typename T>
::std::enable_if_t<::tools::is_rational_v<T> || ::std::is_floating_point_v<T>, ::std::optional<::std::variant<::tools::vector2<T>, ::tools::half_line_2d<T>>>>
operator&(const ::tools::half_line_2d<T>& lhs, const ::tools::line_2d<T>& rhs) {
using variant_t = ::std::variant<::tools::vector2<T>, ::tools::half_line_2d<T>>;
using result_t = ::std::optional<variant_t>;
const auto lhs_line = lhs.to_line();
if (lhs_line == rhs) return result_t(variant_t(lhs));
const auto possible_cross_point = lhs_line.cross_point(rhs);
return possible_cross_point && lhs.m_d.inner_product(*possible_cross_point - lhs.m_a) >= T(0)
? result_t(variant_t(*possible_cross_point))
: ::std::nullopt;
}
template <typename T>
bool operator==(const ::tools::half_line_2d<T>& lhs, const ::tools::half_line_2d<T>& rhs) {
return lhs.a() == rhs.a() && lhs.d().x * rhs.d().y == rhs.d().x * lhs.d().y;
}
template <typename T>
bool operator!=(const ::tools::half_line_2d<T>& lhs, const ::tools::half_line_2d<T>& rhs) {
return !(lhs == rhs);
}
template <typename T>
line_2d<T>::line_2d(const T& a, const T& b, const T& c) :
m_a(a),
m_b(b),
m_c(c) {
assert(a != T(0) || b != T(0));
}
template <typename T>
const T& line_2d<T>::a() const {
return this->m_a;
}
template <typename T>
const T& line_2d<T>::b() const {
return this->m_b;
}
template <typename T>
const T& line_2d<T>::c() const {
return this->m_c;
}
template <typename T>
bool line_2d<T>::contains(const ::tools::vector2<T>& p) const {
return this->m_a * p.x + this->m_b * p.y + this->m_c == T(0);
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
line_2d<T>::cross_point(const ::tools::directed_line_segment_2d<T>& other) const {
return other.cross_point(*this);
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
line_2d<T>::cross_point(const ::tools::half_line_2d<T>& other) const {
return other.cross_point(*this);
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::std::optional<::tools::vector2<T>>>
line_2d<T>::cross_point(const ::tools::line_2d<T>& other) const {
using result_t = ::std::optional<::tools::vector2<T>>;
if (!this->crosses(other)) return ::std::nullopt;
return result_t(::tools::vector2<T>(
(this->m_b * other.m_c - other.m_b * this->m_c) / (this->m_a * other.m_b - other.m_a * this->m_b),
(other.m_a * this->m_c - this->m_a * other.m_c) / (this->m_a * other.m_b - other.m_a * this->m_b)
));
}
template <typename T>
bool line_2d<T>::crosses(const ::tools::line_2d<T>& other) const {
return this->m_a * other.m_b != other.m_a * this->m_b;
}
template <typename T>
bool line_2d<T>::is_parallel_to(const ::tools::line_2d<T>& other) const {
return this->m_a * other.m_b == this->m_b * other.m_a;
}
template <typename T>
::tools::vector2<T> line_2d<T>::normal() const {
return ::tools::vector2<T>(this->m_a, this->m_b);
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::tools::vector2<T>>
line_2d<T>::projection(const ::tools::vector2<T>& p) const {
return *::tools::half_line_2d<T>(p, this->normal()).to_line().cross_point(*this);
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
line_2d<T>::squared_distance(const ::tools::directed_line_segment_2d<T>& other) const {
return other.squared_distance(*this);
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
line_2d<T>::squared_distance(const ::tools::half_line_2d<T>& other) const {
return other.squared_distance(*this);
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
line_2d<T>::squared_distance(const ::tools::line_2d<T>& other) const {
if (this->is_parallel_to(other)) {
return ::tools::square(other.m_a * this->m_c - this->m_a * other.m_c) / (::tools::square(this->m_a) + ::tools::square(this->m_b)) / ::tools::square(other.m_a);
} else {
return T(0);
}
}
template <typename T> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, T>
line_2d<T>::squared_distance(const ::tools::vector2<T>& p) const {
return (p - this->projection(p)).squared_l2_norm();
}
template <typename T, bool HasRadius>
::std::enable_if_t<::std::is_floating_point_v<T>, ::std::vector<::tools::vector2<T>>>
operator&(const ::tools::line_2d<T>& lhs, const ::tools::circle_2d<T, false, HasRadius>& rhs) {
return rhs & lhs;
}
template <typename T, bool HasRadius>
::std::enable_if_t<::std::is_floating_point_v<T>, ::std::optional<::std::variant<::tools::vector2<T>, ::tools::directed_line_segment_2d<T>>>>
operator&(const ::tools::line_2d<T>& lhs, const ::tools::circle_2d<T, true, HasRadius>& rhs) {
return rhs & lhs;
}
template <typename T>
::std::enable_if_t<::tools::is_rational_v<T> || ::std::is_floating_point_v<T>, ::std::optional<::std::variant<::tools::vector2<T>, ::tools::directed_line_segment_2d<T>>>>
operator&(const ::tools::line_2d<T>& lhs, const ::tools::directed_line_segment_2d<T>& rhs) {
return rhs & lhs;
}
template <typename T>
::std::enable_if_t<::tools::is_rational_v<T> || ::std::is_floating_point_v<T>, ::std::optional<::std::variant<::tools::vector2<T>, ::tools::half_line_2d<T>>>>
operator&(const ::tools::line_2d<T>& lhs, const ::tools::half_line_2d<T>& rhs) {
return rhs & lhs;
}
template <typename T>
::std::enable_if_t<::tools::is_rational_v<T> || ::std::is_floating_point_v<T>, ::std::optional<::std::variant<::tools::vector2<T>, ::tools::line_2d<T>>>>
operator&(const ::tools::line_2d<T>& lhs, const ::tools::line_2d<T>& rhs) {
using variant_t = ::std::variant<::tools::vector2<T>, ::tools::line_2d<T>>;
using result_t = ::std::optional<variant_t>;
if (lhs == rhs) return result_t(variant_t(lhs));
const auto possible_cross_point = lhs.cross_point(rhs);
return possible_cross_point ? result_t(variant_t(*possible_cross_point)) : ::std::nullopt;
}
template <typename T>
bool operator==(const ::tools::line_2d<T>& lhs, const ::tools::line_2d<T>& rhs) {
return lhs.m_b * rhs.m_c == lhs.m_c * rhs.m_b && lhs.m_c * rhs.m_a == lhs.m_a * rhs.m_c && lhs.m_a * rhs.m_b == lhs.m_b * rhs.m_a;
}
template <typename T>
bool operator!=(const ::tools::line_2d<T>& lhs, const ::tools::line_2d<T>& rhs) {
return !(lhs == rhs);
}
template <typename T>
::tools::line_2d<T> line_2d<T>::through(const ::tools::vector2<T>& p1, const ::tools::vector2<T>& p2) {
return ::tools::line_2d<T>(p1.y - p2.y, p2.x - p1.x, (p2.y - p1.y) * p1.x - (p2.x - p1.x) * p1.y);
}
template <typename T, bool Filled>
T polygon_2d<T, Filled>::doubled_signed_area() const {
T result(0);
for (::std::size_t i = 0; i < this->m_points.size(); ++i) {
result += (this->m_points[i].x - this->m_points[(i + 1) % this->m_points.size()].x) * (this->m_points[i].y + this->m_points[(i + 1) % this->m_points.size()].y);
}
return result;
}
template <typename T, bool Filled>
template <typename InputIterator>
polygon_2d<T, Filled>::polygon_2d(const InputIterator& begin, const InputIterator& end) : m_points(begin, end) {
assert(this->m_points.size() >= 3);
}
template <typename T, bool Filled>
polygon_2d<T, Filled>::polygon_2d(::std::initializer_list<::tools::vector2<T>> init) : polygon_2d(init.begin(), init.end()) {
}
template <typename T, bool Filled> template <typename T_, bool Filled_>
::std::enable_if_t<(::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>) && Filled_, T> polygon_2d<T, Filled>::area() const {
return this->doubled_area() / T(2);
}
template <typename T, bool Filled> template <bool Filled_>
::std::enable_if_t<Filled_, T> polygon_2d<T, Filled>::doubled_area() const {
return ::tools::abs(this->doubled_signed_area());
}
template <typename T, bool Filled>
bool polygon_2d<T, Filled>::is_counterclockwise() const {
return this->doubled_signed_area() > T(0);
}
template <typename T, bool Filled> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::tools::circle_2d<T, Filled, false>> polygon_2d<T, Filled>::minimum_bounding_circle() const {
::std::optional<::tools::circle_2d<T, Filled, false>> answer;
for (::std::size_t i = 0; i < this->m_points.size(); ++i) {
for (::std::size_t j = i + 1; j < this->m_points.size(); ++j) {
for (::std::size_t k = j + 1; k < this->m_points.size(); ++k) {
if (const auto possible_answer = ::tools::triangle_2d<T, Filled>({this->m_points[i], this->m_points[j], this->m_points[k]}).minimum_bounding_circle();
!answer || answer->squared_radius() < possible_answer.squared_radius()) {
answer = ::std::move(possible_answer);
}
}
}
}
return *answer;
}
template <typename T, bool Filled>
int polygon_2d<T, Filled>::where(const ::tools::vector2<T>& p) const {
::std::vector<::tools::directed_line_segment_2d<T>> edges;
for (::std::size_t i = 0; i < this->m_points.size(); ++i) {
edges.emplace_back(this->m_points[i], this->m_points[(i + 1) % this->m_points.size()]);
}
if (std::any_of(edges.begin(), edges.end(), [&](const auto& edge) { return edge.contains(p); })) {
return 0;
} else {
bool in = false;
for (const auto& edge : edges) {
if ([&]() {
const auto l = edge.to_line();
if (l == ::tools::line_2d<T>(T(0), T(1), -p.y)) return false;
if (p.x <= edge.p1().x && p.y == edge.p1().y) return edge.p2().y < edge.p1().y;
if (p.x <= edge.p2().x && p.y == edge.p2().y) return edge.p1().y < edge.p2().y;
if ((edge.p1().y - p.y) * (edge.p2().y - p.y) > T(0)) return false;
return l.a() * (l.a() * p.x + l.b() * p.y + l.c()) < T(0);
}()) {
in = !in;
}
}
return in ? 1 : -1;
}
}
template <typename T, bool Filled>
template <typename OutputIterator>
void triangle_2d<T, Filled>::sorted_edges(OutputIterator result) const {
::std::array<::tools::directed_line_segment_2d<T>, 3> edges;
for (int i = 0; i < 3; ++i) {
edges[i] = ::tools::directed_line_segment_2d<T>(this->m_points[i], this->m_points[(i + 1) % 3]);
}
::std::sort(edges.begin(), edges.end(), ::tools::less_by([](const auto& edge) {
return edge.squared_length();
}));
for (const auto& edge : edges) {
*result = edge;
++result;
}
}
template <typename T, bool Filled>
template <typename InputIterator>
triangle_2d<T, Filled>::triangle_2d(const InputIterator& begin, const InputIterator& end) : polygon_2d<T, Filled>(begin, end) {
assert(this->m_points.size() == 3);
}
template <typename T, bool Filled>
triangle_2d<T, Filled>::triangle_2d(::std::initializer_list<::tools::vector2<T>> init) : triangle_2d(init.begin(), init.end()) {
}
template <typename T, bool Filled> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::tools::circle_2d<T, Filled, false>> triangle_2d<T, Filled>::circumcircle() const {
const auto& A = this->m_points[0];
const auto& B = this->m_points[1];
const auto& C = this->m_points[2];
const auto a2 = (C - B).squared_l2_norm();
const auto b2 = (A - C).squared_l2_norm();
const auto c2 = (B - A).squared_l2_norm();
const auto kA = a2 * (b2 + c2 - a2);
const auto kB = b2 * (c2 + a2 - b2);
const auto kC = c2 * (a2 + b2 - c2);
const auto circumcenter = (kA * A + kB * B + kC * C) / (kA + kB + kC);
return ::tools::circle_2d<T, Filled, false>(circumcenter, (circumcenter - A).squared_l2_norm());
}
template <typename T, bool Filled> template <typename T_>
::std::enable_if_t<::std::is_floating_point_v<T_>, ::tools::circle_2d<T, Filled>> triangle_2d<T, Filled>::incircle() const {
const auto& A = this->m_points[0];
const auto& B = this->m_points[1];
const auto& C = this->m_points[2];
const auto a = (C - B).l2_norm();
const auto b = (A - C).l2_norm();
const auto c = (B - A).l2_norm();
const auto incenter = (a * A + b * B + c * C) / (a + b + c);
return ::tools::circle_2d<T, Filled>(incenter, ::tools::abs(this->doubled_signed_area()) / (a + b + c));
}
template <typename T, bool Filled> template <typename T_>
::std::enable_if_t<::tools::is_rational_v<T_> || ::std::is_floating_point_v<T_>, ::tools::circle_2d<T, Filled, false>> triangle_2d<T, Filled>::minimum_bounding_circle() const {
::std::array<::tools::directed_line_segment_2d<T>, 3> edges;
this->sorted_edges(edges.begin());
if (edges[0].squared_length() + edges[1].squared_length() <= edges[2].squared_length()) {
const auto center = edges[2].midpoint();
return ::tools::circle_2d<T, Filled, false>(center, (center - edges[2].p1()).squared_l2_norm());
} else {
return this->circumcircle();
}
}
template <typename T, bool Filled>
int triangle_2d<T, Filled>::type() const {
::std::array<::tools::directed_line_segment_2d<T>, 3> edges;
this->sorted_edges(edges.begin());
const auto c2 = edges[2].squared_length();
const auto a2b2 = edges[1].squared_length() + edges[0].squared_length();
if (c2 < a2b2) {
return 0;
} else if (c2 == a2b2) {
return 1;
} else {
return 2;
}
}
}