proconlib

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

View the Project on GitHub anqooqie/proconlib

:heavy_check_mark: tests/triangle_2d/circumcircle/double.test.cpp

Depends on

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/CGL_7_C
// competitive-verifier: ERROR 1e-6

#include <array>
#include <cmath>
#include <iomanip>
#include <iostream>
#include "tools/triangle_2d.hpp"
#include "tools/vector2.hpp"

using T = double;

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

  std::array<tools::vector2<T>, 3> p;
  std::cin >> p[0] >> p[1] >> p[2];
  const auto circumcircle = tools::triangle_2d<T, false>(p).circumcircle();
  std::cout << std::fixed << std::setprecision(10) << circumcircle.center().x << ' ' << circumcircle.center().y << ' ' << std::sqrt(circumcircle.squared_radius()) << '\n';

  return 0;
}

#line 1 "tests/triangle_2d/circumcircle/double.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/CGL_7_C
// competitive-verifier: ERROR 1e-6

#include <array>
#include <cmath>
#include <iomanip>
#include <iostream>
#line 1 "tools/triangle_2d.hpp"



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



#include <algorithm>
#line 6 "tools/detail/geometry_2d.hpp"
#include <cassert>
#line 8 "tools/detail/geometry_2d.hpp"
#include <concepts>
#include <cstddef>
#include <initializer_list>
#include <iterator>
#include <limits>
#include <optional>
#include <random>
#include <ranges>
#include <tuple>
#include <type_traits>
#include <utility>
#include <variant>
#include <vector>
#line 1 "tools/abs.hpp"



#line 7 "tools/abs.hpp"

namespace tools {
  namespace detail::abs {
    template <typename T>
    struct impl {
      constexpr decltype(auto) operator()(const T x) const noexcept(noexcept(std::abs(x))) {
        return std::abs(x);
      }
    };
  }

  template <typename T>
  constexpr decltype(auto) abs(T&& x) noexcept(noexcept(tools::detail::abs::impl<std::remove_cvref_t<T>>{}(std::forward<T>(x)))) {
    return tools::detail::abs::impl<std::remove_cvref_t<T>>{}(std::forward<T>(x));
  }
}


#line 1 "tools/ccw.hpp"



#line 1 "tools/vector2.hpp"



#line 1 "tools/vector.hpp"



#line 10 "tools/vector.hpp"
#include <functional>
#line 15 "tools/vector.hpp"
#include <string>
#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 22 "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;
        members() = default;
        members(const T& x, const T& y) : x(x), y(y) {}
        members(const std::initializer_list<T> il) : 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;
        members() = default;
        members(const T& x, const T& y, const T& z) : x(x), y(y), z(z) {}
        members(const std::initializer_list<T> il) : 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;
        members() = default;
        members(const T& x, const T& y, const T& z, const T& w) : x(x), y(y), z(z), w(w) {}
        members(const std::initializer_list<T> il) : 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 <std::input_iterator 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> {
    using Base = tools::detail::vector::members<T, N>;
    using F = std::conditional_t<std::floating_point<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 {
      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(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 {
      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 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;
    explicit vector(size_type n) requires (variable_sized) : Base(n) {}
    vector(size_type n, const_reference value) requires (variable_sized) : Base(n, value) {}
    template <std::input_iterator InputIter>
    vector(const InputIter first, const InputIter last) requires (variable_sized) : Base(first, last) {}
    vector(const T& x, const T& y) requires (N == 2) : Base(x, y) {}
    vector(const T& x, const T& y, const T& z) requires (N == 3) : Base(x, y, z) {}
    vector(const T& x, const T& y, const T& z, const T& w) requires (N == 4) : 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 {
      if constexpr (variable_sized) {
        return this->m_values.size();
      } else {
        return N;
      }
    }
    bool empty() const noexcept {
      if constexpr (variable_sized) {
        return this->m_values.empty();
      } else {
        return N == 0;
      }
    }

    auto operator[](this auto&& self, const size_type n) -> std::conditional_t<std::is_const_v<std::remove_reference_t<decltype(self)>>, const_reference, reference> {
      assert(n < self.size());
      if constexpr (has_aliases) {
        if constexpr (N == 2) {
          switch (n) {
            case 0: return self.x;
            default: return self.y;
          }
        } else if constexpr (N == 3) {
          switch (n) {
            case 0: return self.x;
            case 1: return self.y;
            default: return self.z;
          }
        } else {
          switch (n) {
            case 0: return self.x;
            case 1: return self.y;
            case 2: return self.z;
            default: return self.w;
          }
        }
      } else {
        return self.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()));
    }
    V normalized() const requires std::floating_point<T> {
      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;
    }

    T outer_product(const V& other) const requires (N == 2) {
      return this->x * other.y - this->y * other.x;
    }
    V turned90() const requires (N == 2) {
      return V{-this->y, this->x};
    }
    V turned270() const requires (N == 2) {
      return V{this->y, -this->x};
    }

    static const std::array<V, 4>& four_directions() requires (N == 2) {
      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;
    }
    static const std::array<V, 8>& eight_directions() requires (N == 2) {
      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;
    }

    V outer_product(const V& other) const requires (N == 3) {
      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};
    }
    std::array<V, 3> orthonormal_basis() const requires (N == 3 && std::floating_point<T>) {
      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 5 "tools/ccw.hpp"

namespace tools {
  template <typename T>
  int ccw(const tools::vector2<T>& a, tools::vector2<T> b, tools::vector2<T> c) {
    b -= a;
    c -= a;
    if (b.outer_product(c) > T(0)) return +1;
    if (b.outer_product(c) < T(0)) return -1;
    if (b.inner_product(c) < T(0)) return +2;
    if (b.squared_l2_norm() < c.squared_l2_norm()) return -2;
    return 0;
  }
}


#line 1 "tools/getter_result.hpp"



#line 5 "tools/getter_result.hpp"

namespace tools {
  template <typename T, typename U>
  struct getter_result {
    using type = std::conditional_t<std::is_lvalue_reference_v<T>, const U&, U>;
  };

  template <typename T, typename U>
  using getter_result_t = typename tools::getter_result<T, U>::type;
}


#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"



#line 5 "tools/less_by.hpp"

namespace tools {

  template <typename F>
  class less_by {
    F m_selector;

  public:
    less_by() = default;
    explicit less_by(const F& selector) : m_selector(selector) {
    }

    template <typename T>
    bool operator()(const T& x, const T& y) const {
      return std::invoke(this->m_selector, x) < std::invoke(this->m_selector, y);
    }
  };
}


#line 1 "tools/signum.hpp"



#line 5 "tools/signum.hpp"
#include <compare>
#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 9 "tools/signum.hpp"

namespace tools {
  namespace detail::signum {
    template <typename T>
    struct impl {
      constexpr int operator()(const T x) const noexcept(noexcept(T(0))) {
        if constexpr (tools::is_unsigned_v<T>) {
          return T(0) < x;
        } else {
          return (T(0) < x) - (x < T(0));
        }
      }
    };
    template <>
    struct impl<std::strong_ordering> {
      constexpr int operator()(const std::strong_ordering x) const noexcept {
        return (0 < x) - (x < 0);
      }
    };
    template <>
    struct impl<std::weak_ordering> {
      constexpr int operator()(const std::weak_ordering x) const noexcept {
        return (0 < x) - (x < 0);
      }
    };
    template <>
    struct impl<std::partial_ordering> {
      constexpr int operator()(const std::partial_ordering x) const noexcept {
        assert(x != std::partial_ordering::unordered);
        return (0 < x) - (x < 0);
      }
    };
  }

  template <typename T>
  constexpr decltype(auto) signum(T&& x) noexcept(noexcept(tools::detail::signum::impl<std::remove_cvref_t<T>>{}(std::forward<T>(x)))) {
    return tools::detail::signum::impl<std::remove_cvref_t<T>>{}(std::forward<T>(x));
  }
}


#line 1 "tools/square.hpp"



#line 1 "tools/monoid.hpp"



#line 5 "tools/monoid.hpp"

namespace tools {
  template <typename M>
  concept monoid = requires(typename M::T x, typename M::T y) {
    { M::op(x, y) } -> std::same_as<typename M::T>;
    { M::e() } -> std::same_as<typename M::T>;
  };
}


#line 5 "tools/square.hpp"

namespace tools {

  template <tools::monoid M>
  constexpr typename M::T square(const typename M::T& x) noexcept(noexcept(M::op(x, x))) {
    return M::op(x, x);
  }

  template <typename T>
  requires (!tools::monoid<T>)
  constexpr T square(const T& x) noexcept(noexcept(x * x)) {
    return x * x;
  }
}


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

namespace tools {
  template <typename T, bool Filled, bool HasRadius = true>
  class circle_2d;

  template <typename T, bool Filled>
  class circumcircle_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);
    explicit circle_2d(const tools::circumcircle_2d<T, Filled>& circumcircle)
    requires std::floating_point<T> || (!HasRadius && tools::is_rational_v<T>);

    T area() const
    requires std::floating_point<T> && Filled;
    auto center(this auto&& self) -> tools::getter_result_t<decltype(self), tools::vector2<T>>;
    bool contains(const tools::vector2<T>& p) const;
    auto radius(this auto&& self) -> tools::getter_result_t<decltype(self), T>
    requires HasRadius;
    auto squared_radius(this auto&& self) -> tools::getter_result_t<decltype(self), T>;
    std::pair<int, int> where(const tools::circle_2d<T, Filled, HasRadius>& other) const;
    int where(const tools::vector2<T>& p) const;

    template <std::floating_point T_, bool HasRadius_>
    friend 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 <std::floating_point T_, bool HasRadius_>
    friend std::vector<tools::vector2<T_>>
    operator&(const tools::circle_2d<T_, false, HasRadius_>& lhs, const tools::line_2d<T_>& rhs);
    template <std::floating_point T_, bool HasRadius_>
    friend 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, bool Filled>
  class circumcircle_2d {
    std::vector<tools::vector2<T>> m_points;

  public:
    circumcircle_2d() = default;
    template <std::ranges::input_range R>
    requires std::assignable_from<tools::vector2<T>&, std::ranges::range_reference_t<R>>
    circumcircle_2d(R&& p);
    circumcircle_2d(std::initializer_list<tools::vector2<T>> p);

    T area() const
    requires std::floating_point<T> && Filled;
    tools::vector2<T> center() const
    requires std::floating_point<T> || tools::is_rational_v<T>;
    bool contains(const tools::vector2<T>& p) const;
    auto points(this auto&& self) -> tools::getter_result_t<decltype(self), std::vector<tools::vector2<T>>>;
    T radius() const
    requires std::floating_point<T>;
    T squared_radius() const
    requires std::floating_point<T> || tools::is_rational_v<T>;
    int where(const tools::vector2<T>& p) const;
  };

  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; 
    std::optional<tools::vector2<T>> cross_point(const tools::directed_line_segment_2d<T>& other) const
    requires tools::is_rational_v<T> || std::floating_point<T>;
    std::optional<tools::vector2<T>> cross_point(const tools::half_line_2d<T>& other) const
    requires tools::is_rational_v<T> || std::floating_point<T>;
    std::optional<tools::vector2<T>> cross_point(const tools::line_2d<T>& other) const
    requires tools::is_rational_v<T> || std::floating_point<T>;
    bool crosses(const tools::directed_line_segment_2d<T>& other) const;
    tools::vector2<T> midpoint() const
    requires tools::is_rational_v<T> || std::floating_point<T>;
    auto p1(this auto&& self) -> tools::getter_result_t<decltype(self), tools::vector2<T>>;
    auto p2(this auto&& self) -> tools::getter_result_t<decltype(self), tools::vector2<T>>;
    T squared_distance(const tools::directed_line_segment_2d<T>& other) const
    requires tools::is_rational_v<T> || std::floating_point<T>;
    T squared_distance(const tools::half_line_2d<T>& other) const
    requires tools::is_rational_v<T> || std::floating_point<T>;
    T squared_distance(const tools::line_2d<T>& other) const
    requires tools::is_rational_v<T> || std::floating_point<T>;
    T squared_distance(const tools::vector2<T>& p) const
    requires tools::is_rational_v<T> || std::floating_point<T>;
    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_>
    requires tools::is_rational_v<T_> || std::floating_point<T_>
    friend 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_>
    requires tools::is_rational_v<T_> || std::floating_point<T_>
    friend 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_>
    requires tools::is_rational_v<T_> || std::floating_point<T_>
    friend 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);

    auto a(this auto&& self) -> tools::getter_result_t<decltype(self), tools::vector2<T>>;
    bool contains(const tools::vector2<T>& p) const;
    std::optional<tools::vector2<T>> cross_point(const tools::directed_line_segment_2d<T>& other) const
    requires tools::is_rational_v<T> || std::floating_point<T>;
    std::optional<tools::vector2<T>> cross_point(const tools::half_line_2d<T>& other) const
    requires tools::is_rational_v<T> || std::floating_point<T>;
    std::optional<tools::vector2<T>> cross_point(const tools::line_2d<T>& other) const
    requires tools::is_rational_v<T> || std::floating_point<T>;
    auto d(this auto&& self) -> tools::getter_result_t<decltype(self), tools::vector2<T>>;
    T squared_distance(const tools::directed_line_segment_2d<T>& other) const
    requires tools::is_rational_v<T> || std::floating_point<T>;
    T squared_distance(const tools::half_line_2d<T>& other) const
    requires tools::is_rational_v<T> || std::floating_point<T>;
    T squared_distance(const tools::line_2d<T>& other) const
    requires tools::is_rational_v<T> || std::floating_point<T>;
    T squared_distance(const tools::vector2<T>& p) const
    requires tools::is_rational_v<T> || std::floating_point<T>;
    tools::line_2d<T> to_line() const;

    template <typename T_>
    requires tools::is_rational_v<T_> || std::floating_point<T_>
    friend 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_>
    requires tools::is_rational_v<T_> || std::floating_point<T_>
    friend 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_>
    requires tools::is_rational_v<T_> || std::floating_point<T_>
    friend 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);

    auto a(this auto&& self) -> tools::getter_result_t<decltype(self), T>;
    auto b(this auto&& self) -> tools::getter_result_t<decltype(self), T>;
    auto c(this auto&& self) -> tools::getter_result_t<decltype(self), T>;
    bool contains(const tools::vector2<T>& p) const;
    std::optional<tools::vector2<T>> cross_point(const tools::directed_line_segment_2d<T>& other) const
    requires tools::is_rational_v<T> || std::floating_point<T>;
    std::optional<tools::vector2<T>> cross_point(const tools::half_line_2d<T>& other) const
    requires tools::is_rational_v<T> || std::floating_point<T>;
    std::optional<tools::vector2<T>> cross_point(const tools::line_2d<T>& other) const
    requires tools::is_rational_v<T> || std::floating_point<T>;
    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;
    tools::vector2<T> projection(const tools::vector2<T>& p) const
    requires tools::is_rational_v<T> || std::floating_point<T>;
    T squared_distance(const tools::directed_line_segment_2d<T>& other) const
    requires tools::is_rational_v<T> || std::floating_point<T>;
    T squared_distance(const tools::half_line_2d<T>& other) const
    requires tools::is_rational_v<T> || std::floating_point<T>;
    T squared_distance(const tools::line_2d<T>& other) const
    requires tools::is_rational_v<T> || std::floating_point<T>;
    T squared_distance(const tools::vector2<T>& p) const
    requires tools::is_rational_v<T> || std::floating_point<T>;

    template <std::floating_point T_, bool HasRadius_>
    friend std::vector<tools::vector2<T_>>
    operator&(const tools::line_2d<T_>& lhs, const tools::circle_2d<T_, false, HasRadius_>& rhs);
    template <std::floating_point T_, bool HasRadius_>
    friend 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_>
    requires tools::is_rational_v<T_> || std::floating_point<T_>
    friend 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_>
    requires tools::is_rational_v<T_> || std::floating_point<T_>
    friend 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_>
    requires tools::is_rational_v<T_> || std::floating_point<T_>
    friend 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 <std::ranges::input_range R>
    requires std::assignable_from<tools::vector2<T>&, std::ranges::range_reference_t<R>>
    polygon_2d(R&& p);
    polygon_2d(std::initializer_list<tools::vector2<T>> p);

    T area() const
    requires (tools::is_rational_v<T> || std::floating_point<T>) && Filled;
    T doubled_area() const
    requires Filled;
    bool is_counterclockwise() const;
    tools::circumcircle_2d<T, Filled> minimum_bounding_circle() const;
    auto points(this auto&& self) -> tools::getter_result_t<decltype(self), std::vector<tools::vector2<T>>>;
    int where(const tools::vector2<T>& p) const;
  };

  template <typename T, bool Filled>
  class triangle_2d : public polygon_2d<T, Filled> {
    std::array<tools::directed_line_segment_2d<T>, 3> sorted_edges() const;

  public:
    triangle_2d() = default;
    template <std::ranges::input_range R>
    requires std::assignable_from<tools::vector2<T>&, std::ranges::range_reference_t<R>>
    triangle_2d(R&& p);
    triangle_2d(std::initializer_list<tools::vector2<T>> p);

    tools::circumcircle_2d<T, Filled> circumcircle() const;
    tools::circle_2d<T, Filled> incircle() const
    requires std::floating_point<T>;
    tools::circumcircle_2d<T, Filled> 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>
  circle_2d<T, Filled, HasRadius>::circle_2d(const tools::circumcircle_2d<T, Filled>& circumcircle)
  requires std::floating_point<T> || (!HasRadius && tools::is_rational_v<T>)
  : m_center(circumcircle.center()), m_squared_radius(circumcircle.squared_radius()) {
    if constexpr (HasRadius) {
      this->m_radius = std::sqrt(this->m_squared_radius);
    }
  }

  template <typename T, bool Filled, bool HasRadius>
  T circle_2d<T, Filled, HasRadius>::area() const requires std::floating_point<T> && Filled {
    return std::acos(T(-1)) * this->m_squared_radius;
  }

  template <typename T, bool Filled, bool HasRadius>
  auto circle_2d<T, Filled, HasRadius>::center(this auto&& self) -> tools::getter_result_t<decltype(self), tools::vector2<T>> {
    return std::forward_like<decltype(self)>(self.m_center);
  }

  template <typename T, bool Filled, bool HasRadius>
  bool circle_2d<T, Filled, HasRadius>::contains(const tools::vector2<T>& p) const {
    if constexpr (Filled) {
      return this->where(p) >= 0;
    } else {
      return this->where(p) == 0;
    }
  }

  template <typename T, bool Filled, bool HasRadius>
  auto circle_2d<T, Filled, HasRadius>::radius(this auto&& self) -> tools::getter_result_t<decltype(self), T>
  requires HasRadius {
    return std::forward_like<decltype(self)>(self.m_radius);
  }

  template <typename T, bool Filled, bool HasRadius>
  auto circle_2d<T, Filled, HasRadius>::squared_radius(this auto&& self) -> tools::getter_result_t<decltype(self), T> {
    return std::forward_like<decltype(self)>(self.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 <std::floating_point T, bool HasRadius>
  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 <std::floating_point T, bool HasRadius>
  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 <std::floating_point T, bool HasRadius>
  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, bool Filled>
  template <std::ranges::input_range R>
  requires std::assignable_from<tools::vector2<T>&, std::ranges::range_reference_t<R>>
  circumcircle_2d<T, Filled>::circumcircle_2d(R&& p) : m_points(std::forward<R>(p) | std::ranges::to<std::vector<tools::vector2<T>>>()) {
    assert(this->m_points.size() == 2 || this->m_points.size() == 3);
    if (this->m_points.size() == 2) {
      assert(this->m_points[0] != this->m_points[1]);
    } else {
      const auto ccw = tools::ccw(this->m_points[0], this->m_points[1], this->m_points[2]);
      assert(std::abs(ccw) == 1);
      if (ccw == -1) {
        std::swap(this->m_points[1], this->m_points[2]);
      }
    }
  }

  template <typename T, bool Filled>
  circumcircle_2d<T, Filled>::circumcircle_2d(std::initializer_list<tools::vector2<T>> p) : circumcircle_2d(std::views::all(p)) {
  }

  template <typename T, bool Filled>
  T circumcircle_2d<T, Filled>::area() const
  requires std::floating_point<T> && Filled {
    return std::acos(T(-1)) * this->squared_radius();
  }

  template <typename T, bool Filled>
  tools::vector2<T> circumcircle_2d<T, Filled>::center() const
  requires std::floating_point<T> || tools::is_rational_v<T> {
    if (this->m_points.size() == 2) {
      return (this->m_points[0] + this->m_points[1]) / T(2);
    } else {
      const auto u = this->m_points[1] - this->m_points[0];
      const auto v = this->m_points[2] - this->m_points[0];
      const auto shifted_circumcenter = (v.squared_l2_norm() * u - u.squared_l2_norm() * v).turned90() / (T(2) * u.outer_product(v));
      return this->m_points[0] + shifted_circumcenter;
    }
  }

  template <typename T, bool Filled>
  bool circumcircle_2d<T, Filled>::contains(const tools::vector2<T>& p) const {
    if constexpr (Filled) {
      return this->where(p) >= 0;
    } else {
      return this->where(p) == 0;
    }
  }

  template <typename T, bool Filled>
  auto circumcircle_2d<T, Filled>::points(this auto&& self) -> tools::getter_result_t<decltype(self), std::vector<tools::vector2<T>>> {
    return std::forward_like<decltype(self)>(self.m_points);
  }

  template <typename T, bool Filled>
  T circumcircle_2d<T, Filled>::radius() const
  requires std::floating_point<T> {
    return std::sqrt(this->squared_radius());
  }

  template <typename T, bool Filled>
  T circumcircle_2d<T, Filled>::squared_radius() const
  requires std::floating_point<T> || tools::is_rational_v<T> {
    return (this->m_points[0] - this->center()).squared_l2_norm();
  }

  template <typename T, bool Filled>
  int circumcircle_2d<T, Filled>::where(const tools::vector2<T>& p) const {
    if (this->m_points.size() == 2) {
      return -tools::signum((this->m_points[0] - p).inner_product(this->m_points[1] - p));
    } else {
      const auto p0 = this->m_points[0] - p;
      const auto p1 = this->m_points[1] - p;
      const auto p2 = this->m_points[2] - p;
      const auto p0sq = p0.squared_l2_norm();
      const auto p1sq = p1.squared_l2_norm();
      const auto p2sq = p2.squared_l2_norm();
      return tools::signum(p0.x * p1.y * p2sq + p0.y * p1sq * p2.x + p0sq * p1.x * p2.y - p0sq * p1.y * p2.x - p0.y * p1.x * p2sq - p0.x * p1sq * p2.y);
    }
  }

  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>
  std::optional<tools::vector2<T>> directed_line_segment_2d<T>::cross_point(const tools::directed_line_segment_2d<T>& other) const
  requires tools::is_rational_v<T> || std::floating_point<T> {
    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>
  std::optional<tools::vector2<T>> directed_line_segment_2d<T>::cross_point(const tools::half_line_2d<T>& other) const
  requires tools::is_rational_v<T> || std::floating_point<T> {
    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>
  std::optional<tools::vector2<T>> directed_line_segment_2d<T>::cross_point(const tools::line_2d<T>& other) const
  requires tools::is_rational_v<T> || std::floating_point<T> {
    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>
  tools::vector2<T> directed_line_segment_2d<T>::midpoint() const
  requires tools::is_rational_v<T> || std::floating_point<T> {
    return (this->m_p1 + this->m_p2) / T(2);
  }

  template <typename T>
  auto directed_line_segment_2d<T>::p1(this auto&& self) -> tools::getter_result_t<decltype(self), tools::vector2<T>> {
    return std::forward_like<decltype(self)>(self.m_p1);
  }

  template <typename T>
  auto directed_line_segment_2d<T>::p2(this auto&& self) -> tools::getter_result_t<decltype(self), tools::vector2<T>> {
    return std::forward_like<decltype(self)>(self.m_p2);
  }

  template <typename T>
  T directed_line_segment_2d<T>::squared_distance(const tools::directed_line_segment_2d<T>& other) const
  requires tools::is_rational_v<T> || std::floating_point<T> {
    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>
  T directed_line_segment_2d<T>::squared_distance(const tools::half_line_2d<T>& other) const
  requires tools::is_rational_v<T> || std::floating_point<T> {
    if (*this & other) {
      return T(0);
    }
    return std::min({
      other.squared_distance(this->m_p1),
      other.squared_distance(this->m_p2)
    });
  }

  template <typename T>
  T directed_line_segment_2d<T>::squared_distance(const tools::line_2d<T>& other) const
  requires tools::is_rational_v<T> || std::floating_point<T> {
    if (*this & other) {
      return T(0);
    }
    return std::min({
      other.squared_distance(this->m_p1),
      other.squared_distance(this->m_p2)
    });
  }

  template <typename T>
  T directed_line_segment_2d<T>::squared_distance(const tools::vector2<T>& p) const
  requires tools::is_rational_v<T> || std::floating_point<T> {
    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>
  requires tools::is_rational_v<T> || std::floating_point<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>
  requires tools::is_rational_v<T> || std::floating_point<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>
  requires tools::is_rational_v<T> || std::floating_point<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>
  auto half_line_2d<T>::a(this auto&& self) -> tools::getter_result_t<decltype(self), tools::vector2<T>> {
    return std::forward_like<decltype(self)>(self.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>
  std::optional<tools::vector2<T>> half_line_2d<T>::cross_point(const tools::directed_line_segment_2d<T>& other) const
  requires tools::is_rational_v<T> || std::floating_point<T> {
    return other.cross_point(*this);
  }

  template <typename T>
  std::optional<tools::vector2<T>> half_line_2d<T>::cross_point(const tools::half_line_2d<T>& other) const
  requires tools::is_rational_v<T> || std::floating_point<T> {
    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>
  std::optional<tools::vector2<T>> half_line_2d<T>::cross_point(const tools::line_2d<T>& other) const
  requires tools::is_rational_v<T> || std::floating_point<T> {
    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>
  auto half_line_2d<T>::d(this auto&& self) -> tools::getter_result_t<decltype(self), tools::vector2<T>> {
    return std::forward_like<decltype(self)>(self.m_d);
  }

  template <typename T>
  T half_line_2d<T>::squared_distance(const tools::directed_line_segment_2d<T>& other) const
  requires tools::is_rational_v<T> || std::floating_point<T> {
    return other.squared_distance(*this);
  }

  template <typename T>
  T half_line_2d<T>::squared_distance(const tools::half_line_2d<T>& other) const
  requires tools::is_rational_v<T> || std::floating_point<T> {
    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>
  T half_line_2d<T>::squared_distance(const tools::line_2d<T>& other) const
  requires tools::is_rational_v<T> || std::floating_point<T> {
    if (*this & other) {
      return T(0);
    }
    return other.squared_distance(this->m_a);
  }

  template <typename T>
  T half_line_2d<T>::squared_distance(const tools::vector2<T>& p) const
  requires tools::is_rational_v<T> || std::floating_point<T> {
    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>
  requires tools::is_rational_v<T> || std::floating_point<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>
  requires tools::is_rational_v<T> || std::floating_point<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>
  requires tools::is_rational_v<T> || std::floating_point<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>
  auto line_2d<T>::a(this auto&& self) -> tools::getter_result_t<decltype(self), T> {
    return std::forward_like<decltype(self)>(self.m_a);
  }

  template <typename T>
  auto line_2d<T>::b(this auto&& self) -> tools::getter_result_t<decltype(self), T> {
    return std::forward_like<decltype(self)>(self.m_b);
  }

  template <typename T>
  auto line_2d<T>::c(this auto&& self) -> tools::getter_result_t<decltype(self), T> {
    return std::forward_like<decltype(self)>(self.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>
  std::optional<tools::vector2<T>> line_2d<T>::cross_point(const tools::directed_line_segment_2d<T>& other) const
  requires tools::is_rational_v<T> || std::floating_point<T> {
    return other.cross_point(*this);
  }

  template <typename T>
  std::optional<tools::vector2<T>> line_2d<T>::cross_point(const tools::half_line_2d<T>& other) const
  requires tools::is_rational_v<T> || std::floating_point<T> {
    return other.cross_point(*this);
  }

  template <typename T>
  std::optional<tools::vector2<T>> line_2d<T>::cross_point(const tools::line_2d<T>& other) const
  requires tools::is_rational_v<T> || std::floating_point<T> {
    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>
  tools::vector2<T> line_2d<T>::projection(const tools::vector2<T>& p) const
  requires tools::is_rational_v<T> || std::floating_point<T> {
    return *tools::half_line_2d<T>(p, this->normal()).to_line().cross_point(*this);
  }

  template <typename T>
  T line_2d<T>::squared_distance(const tools::directed_line_segment_2d<T>& other) const
  requires tools::is_rational_v<T> || std::floating_point<T> {
    return other.squared_distance(*this);
  }

  template <typename T>
  T line_2d<T>::squared_distance(const tools::half_line_2d<T>& other) const
  requires tools::is_rational_v<T> || std::floating_point<T> {
    return other.squared_distance(*this);
  }

  template <typename T>
  T line_2d<T>::squared_distance(const tools::line_2d<T>& other) const
  requires tools::is_rational_v<T> || std::floating_point<T> {
    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>
  T line_2d<T>::squared_distance(const tools::vector2<T>& p) const
  requires tools::is_rational_v<T> || std::floating_point<T> {
    return (p - this->projection(p)).squared_l2_norm();
  }

  template <std::floating_point T, bool HasRadius>
  std::vector<tools::vector2<T>>
  operator&(const tools::line_2d<T>& lhs, const tools::circle_2d<T, false, HasRadius>& rhs) {
    return rhs & lhs;
  }

  template <std::floating_point T, bool HasRadius>
  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>
  requires 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>
  requires 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>
  requires 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 <std::ranges::input_range R>
  requires std::assignable_from<tools::vector2<T>&, std::ranges::range_reference_t<R>>
  polygon_2d<T, Filled>::polygon_2d(R&& p) : m_points(std::forward<R>(p) | std::ranges::to<std::vector<tools::vector2<T>>>()) {
    assert(this->m_points.size() >= 3);
  }

  template <typename T, bool Filled>
  polygon_2d<T, Filled>::polygon_2d(std::initializer_list<tools::vector2<T>> p) : polygon_2d(std::views::all(p)) {
  }

  template <typename T, bool Filled>
  T polygon_2d<T, Filled>::area() const
  requires (tools::is_rational_v<T> || std::floating_point<T>) && Filled {
    return this->doubled_area() / T(2);
  }

  template <typename T, bool Filled>
  T polygon_2d<T, Filled>::doubled_area() const
  requires Filled {
    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>
  tools::circumcircle_2d<T, Filled> polygon_2d<T, Filled>::minimum_bounding_circle() const {
    static std::random_device seed_gen;
    thread_local std::mt19937 engine(seed_gen());

    auto shuffled_points = this->m_points;
    std::ranges::shuffle(shuffled_points, engine);

    using variant_t = std::variant<std::nullptr_t, tools::vector2<T>, tools::circumcircle_2d<T, true>>;
    struct visitor_t {
      tools::vector2<T> p;
      bool operator()(std::nullptr_t) {
        return false;
      }
      bool operator()(const tools::vector2<T>& c) {
        return c == this->p;
      }
      bool operator()(const tools::circumcircle_2d<T, true>& c) {
        return c.contains(this->p);
      }
    };

    variant_t res = nullptr;
    for (int i = 0; i < std::ssize(shuffled_points); ++i) {
      if (std::visit(visitor_t{shuffled_points[i]}, res)) continue;
      res = shuffled_points[i];
      for (int j = 0; j < i; ++j) {
        if (std::visit(visitor_t{shuffled_points[j]}, res)) continue;
        res = tools::circumcircle_2d<T, true>{shuffled_points[i], shuffled_points[j]};
        for (int k = 0; k < j; ++k) {
          if (std::visit(visitor_t{shuffled_points[k]}, res)) continue;
          res = tools::circumcircle_2d<T, true>{shuffled_points[i], shuffled_points[j], shuffled_points[k]};
        }
      }
    }

    struct {
      tools::circumcircle_2d<T, Filled> operator()(std::nullptr_t) {
        return tools::circumcircle_2d<T, Filled>{};
      }
      tools::circumcircle_2d<T, Filled> operator()(tools::vector2<T>) {
        return tools::circumcircle_2d<T, Filled>{};
      }
      tools::circumcircle_2d<T, Filled> operator()(const tools::circumcircle_2d<T, true>& c) {
        return tools::circumcircle_2d<T, Filled>(c.points());
      }
    } visitor;
    return std::visit(visitor, res);
  }

  template <typename T, bool Filled>
  auto polygon_2d<T, Filled>::points(this auto&& self) -> tools::getter_result_t<decltype(self), std::vector<tools::vector2<T>>> {
    return std::forward_like<decltype(self)>(self.m_points);
  }

  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>
  std::array<tools::directed_line_segment_2d<T>, 3> triangle_2d<T, Filled>::sorted_edges() 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::ranges::sort(edges, tools::less_by(&tools::directed_line_segment_2d<T>::squared_length));
    return edges;
  }

  template <typename T, bool Filled>
  template <std::ranges::input_range R>
  requires std::assignable_from<tools::vector2<T>&, std::ranges::range_reference_t<R>>
  triangle_2d<T, Filled>::triangle_2d(R&& p) : polygon_2d<T, Filled>(std::forward<R>(p)) {
    assert(this->m_points.size() == 3);
    assert(std::abs(tools::ccw(this->m_points[0], this->m_points[1], this->m_points[2])) == 1);
  }

  template <typename T, bool Filled>
  triangle_2d<T, Filled>::triangle_2d(std::initializer_list<tools::vector2<T>> p) : triangle_2d(std::views::all(p)) {
  }

  template <typename T, bool Filled>
  tools::circumcircle_2d<T, Filled> triangle_2d<T, Filled>::circumcircle() const {
    return tools::circumcircle_2d<T, Filled>(this->m_points);
  }

  template <typename T, bool Filled>
  tools::circle_2d<T, Filled> triangle_2d<T, Filled>::incircle() const
  requires std::floating_point<T> {
    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>
  tools::circumcircle_2d<T, Filled> triangle_2d<T, Filled>::minimum_bounding_circle() const {
    const auto edges = this->sorted_edges();
    if (edges[0].squared_length() + edges[1].squared_length() <= edges[2].squared_length()) {
      return tools::circumcircle_2d<T, Filled>{edges[2].p1(), edges[2].p2()};
    } else {
      return this->circumcircle();
    }
  }

  template <typename T, bool Filled>
  int triangle_2d<T, Filled>::type() const {
    const auto edges = this->sorted_edges();
    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/triangle_2d.hpp"


#line 10 "tests/triangle_2d/circumcircle/double.test.cpp"

using T = double;

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

  std::array<tools::vector2<T>, 3> p;
  std::cin >> p[0] >> p[1] >> p[2];
  const auto circumcircle = tools::triangle_2d<T, false>(p).circumcircle();
  std::cout << std::fixed << std::setprecision(10) << circumcircle.center().x << ' ' << circumcircle.center().y << ' ' << std::sqrt(circumcircle.squared_radius()) << '\n';

  return 0;
}

Test cases

Env Name Status Elapsed Memory
g++ 00_sample_00.in :heavy_check_mark: AC 6 ms 4 MB
g++ 00_sample_01.in :heavy_check_mark: AC 5 ms 4 MB
g++ 01_general_00.in :heavy_check_mark: AC 5 ms 4 MB
g++ 01_general_01.in :heavy_check_mark: AC 5 ms 4 MB
g++ 01_general_02.in :heavy_check_mark: AC 5 ms 4 MB
g++ 01_general_03.in :heavy_check_mark: AC 5 ms 4 MB
g++ 02_right_00.in :heavy_check_mark: AC 5 ms 4 MB
g++ 02_right_01.in :heavy_check_mark: AC 5 ms 4 MB
g++ 02_right_02.in :heavy_check_mark: AC 5 ms 4 MB
g++ 02_right_03.in :heavy_check_mark: AC 5 ms 4 MB
g++ 02_right_04.in :heavy_check_mark: AC 5 ms 4 MB
g++ 02_right_05.in :heavy_check_mark: AC 5 ms 4 MB
g++ 03_obtuse_00.in :heavy_check_mark: AC 5 ms 4 MB
g++ 03_obtuse_01.in :heavy_check_mark: AC 5 ms 4 MB
g++ 03_obtuse_02.in :heavy_check_mark: AC 5 ms 4 MB
g++ 03_obtuse_03.in :heavy_check_mark: AC 5 ms 4 MB
g++ 04_isosceles_00.in :heavy_check_mark: AC 5 ms 4 MB
g++ 04_isosceles_01.in :heavy_check_mark: AC 5 ms 4 MB
g++ 04_isosceles_02.in :heavy_check_mark: AC 5 ms 4 MB
g++ 04_isosceles_03.in :heavy_check_mark: AC 5 ms 4 MB
g++ 04_isosceles_04.in :heavy_check_mark: AC 5 ms 4 MB
g++ 04_isosceles_05.in :heavy_check_mark: AC 5 ms 4 MB
g++ 05_extreme_small_00.in :heavy_check_mark: AC 5 ms 4 MB
g++ 05_extreme_small_01.in :heavy_check_mark: AC 5 ms 4 MB
g++ 06_extreme_large_00.in :heavy_check_mark: AC 5 ms 4 MB
g++ 06_extreme_large_01.in :heavy_check_mark: AC 5 ms 4 MB
g++ 06_extreme_large_02.in :heavy_check_mark: AC 5 ms 4 MB
g++ 06_extreme_large_03.in :heavy_check_mark: AC 5 ms 4 MB
g++ 06_extreme_large_04.in :heavy_check_mark: AC 5 ms 4 MB
g++ 06_extreme_large_05.in :heavy_check_mark: AC 5 ms 4 MB
g++ 06_extreme_large_06.in :heavy_check_mark: AC 5 ms 4 MB
g++ 06_extreme_large_07.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 00_sample_00.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 00_sample_01.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 01_general_00.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 01_general_01.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 01_general_02.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 01_general_03.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 02_right_00.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 02_right_01.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 02_right_02.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 02_right_03.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 02_right_04.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 02_right_05.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 03_obtuse_00.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 03_obtuse_01.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 03_obtuse_02.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 03_obtuse_03.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 04_isosceles_00.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 04_isosceles_01.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 04_isosceles_02.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 04_isosceles_03.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 04_isosceles_04.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 04_isosceles_05.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 05_extreme_small_00.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 05_extreme_small_01.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 06_extreme_large_00.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 06_extreme_large_01.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 06_extreme_large_02.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 06_extreme_large_03.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 06_extreme_large_04.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 06_extreme_large_05.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 06_extreme_large_06.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 06_extreme_large_07.in :heavy_check_mark: AC 5 ms 4 MB
Back to top page