proconlib

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub anqooqie/proconlib

:heavy_check_mark: Two-dimensional circle (tools/circle_2d.hpp)

It is a circle.

License

Author

Constructor

template <typename T, bool Filled, bool HasRadius = true>
circle_2d<T, Filled, HasRadius> c(tools::vector2<T> o, T x);

It creates a circle with center $o$. If Filled is true, it consists of both the boundary and the interior. If Filled is false, it consists only of the boundary. If HasRadius is true, the radius of it is $x$. If HasRadius is false, the radius of it is $\sqrt{x}$.

Constraints

Time Complexity

area

T c.area();

It returns the area of $c$.

Constraints

Time Complexity

center

tools::vector2<T> c.center();

It returns $o$.

Constraints

Time Complexity

radius

T c.radius();

It returns $r$.

Constraints

Time Complexity

squared_radius

T c.squared_radius();

It returns $r^2$.

Constraints

Time Complexity

where

std::pair<int, int> c1.where(circle_2d<T, Filled, HasRadius> c2);

It returns the number of common tangent lines between $c_1$ and $c_2$ and the sign of $r_1 - r_2$. In other words, it returns

\[\begin{align*} \left\{\begin{array}{ll} (0, -1) & \text{(if $c_2$ includes $c_1$)}\\ (0, 1) & \text{(if $c_1$ includes $c_2$)}\\ (1, -1) & \text{(if $c_1$ is inscribed in $c_2$)}\\ (1, 1) & \text{(if $c_2$ is inscribed in $c_1$)}\\ (2, -1) & \text{(if $c_1$ and $c_2$ intersects and $r_1 < r_2$)}\\ (2, 0) & \text{(if $c_1$ and $c_2$ intersects and $r_1 = r_2$)}\\ (2, 1) & \text{(if $c_1$ and $c_2$ intersects and $r_1 > r_2$)}\\ (3, -1) & \text{(if $c_1$ and $c_2$ are cicumscribed and $r_1 < r_2$)}\\ (3, 0) & \text{(if $c_1$ and $c_2$ are cicumscribed and $r_1 = r_2$)}\\ (3, 1) & \text{(if $c_1$ and $c_2$ are cicumscribed and $r_1 > r_2$)}\\ (4, -1) & \text{(if $c_1$ and $c_2$ do not cross and $r_1 < r_2$)}\\ (4, 0) & \text{(if $c_1$ and $c_2$ do not cross and $r_1 = r_2$)}\\ (4, 1) & \text{(if $c_1$ and $c_2$ do not cross and $r_1 > r_2$)}\\ (\infty, 0) & \text{(if $c_1$ is identical to $c_2$)} \end{array}\right.& \end{align*}\]

Constraints

Time Complexity

where

int c.where(tools::vector2<T> p);

It returns

\[\begin{align*} \left\{\begin{array}{ll} -1 & \text{(if $p$ is on the outside of $c$)}\\ 0 & \text{(if $p$ is on the edge of $c$)}\\ 1 & \text{(if $p$ is on the inside of $c$)} \end{array}\right.& \end{align*}\]

Constraints

Time Complexity

operator&

(1) std::optional<std::variant<circle_2d<T, false, HasRadius>, std::vector<tools::vector2<T>>>> operator&(circle_2d<T, false, HasRadius> s, circle_2d<T, false, HasRadius> t);
(2) std::vector<tools::vector2<T>> operator&(circle_2d<T, false> s, tools::line_2d<T> t);
(3) std::optional<std::variant<tools::vector2<T>, tools::directed_line_segment_2d<T>>> operator&(circle_2d<T, true> s, tools::line_2d<T> t);

Constraints

Time Complexity

operator==

bool operator==(circle_2d<T, Filled, HasRadius> c1, circle_2d<T, Filled, HasRadius> c2);

It returns whether $c_1$ is identical to $c_2$ or not.

Constraints

Time Complexity

operator!=

bool operator!=(circle_2d<T, Filled, HasRadius> c1, circle_2d<T, Filled, HasRadius> c2);

It returns !(c1 == c2).

Constraints

Time Complexity

Depends on

Verified with

Code

#ifndef TOOLS_CIRCLE_2D_HPP
#define TOOLS_CIRCLE_2D_HPP

#include "tools/detail/geometry_2d.hpp"

#endif

#line 1 "tools/circle_2d.hpp"



#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;
    }
  }
}


#line 5 "tools/circle_2d.hpp"
Back to top page