proconlib

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

View the Project on GitHub anqooqie/proconlib

:heavy_check_mark: tests/line_2d/is_parallel_to.test.cpp

Depends on

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/CGL_2_A

#include <iostream>
#include "tools/vector2.hpp"
#include "tools/line_2d.hpp"

using ll = long long;
using T = long long;

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  ll q;
  std::cin >> q;
  for (ll i = 0; i < q; ++i) {
    tools::vector2<T> p0, p1, p2, p3;
    std::cin >> p0 >> p1 >> p2 >> p3;

    const auto s1 = tools::line_2d<T>::through(p0, p1);
    const auto s2 = tools::line_2d<T>::through(p2, p3);

    if (s1.is_parallel_to(s2)) {
      std::cout << 2 << '\n';
    } else if (tools::vector2<T>(s1.a(), s1.b()).inner_product(tools::vector2<T>(s2.a(), s2.b())) == T(0)) {
      std::cout << 1 << '\n';
    } else {
      std::cout << 0 << '\n';
    }
  }

  return 0;
}

#line 1 "tests/line_2d/is_parallel_to.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/CGL_2_A

#include <iostream>
#line 1 "tools/vector2.hpp"



#line 1 "tools/vector.hpp"



#include <cstddef>
#include <array>
#include <initializer_list>
#include <cassert>
#include <limits>
#include <vector>
#include <type_traits>
#include <iterator>
#include <algorithm>
#include <utility>
#include <cmath>
#line 16 "tools/vector.hpp"
#include <string>
#include <functional>
#include <tuple>
#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/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 1 "tools/line_2d.hpp"



#line 1 "tools/detail/geometry_2d.hpp"



#line 11 "tools/detail/geometry_2d.hpp"
#include <optional>
#line 15 "tools/detail/geometry_2d.hpp"
#include <variant>
#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 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/line_2d.hpp"


#line 6 "tests/line_2d/is_parallel_to.test.cpp"

using ll = long long;
using T = long long;

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  ll q;
  std::cin >> q;
  for (ll i = 0; i < q; ++i) {
    tools::vector2<T> p0, p1, p2, p3;
    std::cin >> p0 >> p1 >> p2 >> p3;

    const auto s1 = tools::line_2d<T>::through(p0, p1);
    const auto s2 = tools::line_2d<T>::through(p2, p3);

    if (s1.is_parallel_to(s2)) {
      std::cout << 2 << '\n';
    } else if (tools::vector2<T>(s1.a(), s1.b()).inner_product(tools::vector2<T>(s2.a(), s2.b())) == T(0)) {
      std::cout << 1 << '\n';
    } else {
      std::cout << 0 << '\n';
    }
  }

  return 0;
}

Test cases

Env Name Status Elapsed Memory
g++ 00_small_00.in :heavy_check_mark: AC 5 ms 4 MB
g++ 00_small_01.in :heavy_check_mark: AC 4 ms 4 MB
g++ 00_small_02.in :heavy_check_mark: AC 4 ms 4 MB
g++ 00_small_03.in :heavy_check_mark: AC 4 ms 4 MB
g++ 02_horizontal_00.in :heavy_check_mark: AC 4 ms 4 MB
g++ 02_horizontal_01.in :heavy_check_mark: AC 4 ms 4 MB
g++ 03_vertical_00.in :heavy_check_mark: AC 5 ms 4 MB
g++ 03_vertical_01.in :heavy_check_mark: AC 4 ms 4 MB
g++ 04_extreme_00.in :heavy_check_mark: AC 4 ms 4 MB
g++ 04_extreme_01.in :heavy_check_mark: AC 4 ms 4 MB
g++ 05_rand_00.in :heavy_check_mark: AC 4 ms 4 MB
g++ 05_rand_01.in :heavy_check_mark: AC 4 ms 4 MB
g++ 05_rand_02.in :heavy_check_mark: AC 4 ms 4 MB
g++ 05_rand_03.in :heavy_check_mark: AC 4 ms 4 MB
g++ 06_rand_00.in :heavy_check_mark: AC 5 ms 4 MB
g++ 06_rand_01.in :heavy_check_mark: AC 5 ms 4 MB
g++ 06_rand_02.in :heavy_check_mark: AC 5 ms 4 MB
g++ 06_rand_03.in :heavy_check_mark: AC 5 ms 4 MB
g++ 06_rand_04.in :heavy_check_mark: AC 5 ms 4 MB
g++ 06_rand_05.in :heavy_check_mark: AC 5 ms 4 MB
g++ 06_rand_06.in :heavy_check_mark: AC 5 ms 4 MB
g++ 06_rand_07.in :heavy_check_mark: AC 5 ms 4 MB
g++ 06_rand_08.in :heavy_check_mark: AC 4 ms 4 MB
g++ 06_rand_09.in :heavy_check_mark: AC 5 ms 4 MB
g++ 06_rand_10.in :heavy_check_mark: AC 5 ms 4 MB
g++ 06_rand_11.in :heavy_check_mark: AC 5 ms 4 MB
g++ 06_rand_12.in :heavy_check_mark: AC 5 ms 4 MB
g++ 06_rand_13.in :heavy_check_mark: AC 5 ms 4 MB
g++ 07_rand_00.in :heavy_check_mark: AC 5 ms 4 MB
g++ 07_rand_01.in :heavy_check_mark: AC 5 ms 4 MB
g++ 07_rand_02.in :heavy_check_mark: AC 5 ms 4 MB
g++ 07_rand_03.in :heavy_check_mark: AC 5 ms 4 MB
Back to top page