verify/geometry/circle_relation.test.cpp

• View this file on GitHub
• Last update: 2026-10-06 01:57:24+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_7_A

Depends on

• Circles (geometry/circle.hpp)
• geometry/detail/floating_predicate.hpp
• Linear Objects (geometry/linear.hpp)
• 2D Point and Predicates (geometry/point.hpp)
• Fast IO (utilities/fast_io.hpp)

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_7_A"

#include "../../geometry/circle.hpp"

#include <cassert>
#include "../../utilities/fast_io.hpp"

int main() {
    m1une::utilities::FastInput fast_input;
    m1une::utilities::FastOutput fast_output;
    using namespace m1une::geometry;

    Circle<long long> first;
    Circle<long long> second;
    fast_input >> first.center.x >> first.center.y >> first.radius;
    fast_input >> second.center.x >> second.center.y >> second.radius;

    int answer = -1;
    switch (circle_relation(first, second)) {
        case CircleRelation::Separate:
            answer = 4;
            break;
        case CircleRelation::ExternallyTangent:
            answer = 3;
            break;
        case CircleRelation::Intersecting:
            answer = 2;
            break;
        case CircleRelation::InternallyTangent:
            answer = 1;
            break;
        case CircleRelation::Contained:
            answer = 0;
            break;
        case CircleRelation::Coincident:
            assert(false);
    }
    fast_output << answer << '\n';
}

#line 1 "verify/geometry/circle_relation.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_7_A"

#line 1 "geometry/circle.hpp"



#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <cstddef>
#include <numbers>
#include <optional>
#include <type_traits>
#include <vector>

#line 1 "geometry/linear.hpp"



#line 7 "geometry/linear.hpp"

#line 1 "geometry/point.hpp"



#line 5 "geometry/point.hpp"
#include <concepts>
#line 8 "geometry/point.hpp"

#line 1 "geometry/detail/floating_predicate.hpp"



namespace m1une {
namespace geometry {
namespace predicate_detail {

template <typename T>
constexpr T absolute(T value) {
    return value < T(0) ? -value : value;
}

template <typename T>
constexpr T max_value(T first, T second) {
    return first < second ? second : first;
}

template <typename T>
constexpr T vector_scale(T x, T y) {
    return max_value(absolute(x), absolute(y));
}

template <bool Exact, typename T>
constexpr int scaled_sign(T value, T scale, long double eps) {
    if constexpr (Exact) {
        return (value > T(0)) - (value < T(0));
    } else {
        const T tolerance = T(eps) * scale;
        return (value > tolerance) - (value < -tolerance);
    }
}

template <bool Exact, typename T>
constexpr T determinant_scale(T ax, T ay, T bx, T by) {
    if constexpr (Exact) {
        return T(0);
    } else {
        return vector_scale(ax, ay) * vector_scale(bx, by);
    }
}

template <bool Exact, typename T>
constexpr int determinant_sign(
    T ax,
    T ay,
    T bx,
    T by,
    long double eps
) {
    const T determinant = ax * by - ay * bx;
    return scaled_sign<Exact>(
        determinant,
        determinant_scale<Exact>(ax, ay, bx, by),
        eps
    );
}

template <bool Exact, typename T>
constexpr int orientation_sign(
    T direction_x,
    T direction_y,
    T offset_x,
    T offset_y,
    long double eps
) {
    const T determinant =
        direction_x * offset_y - direction_y * offset_x;
    T scale = T(0);
    if constexpr (!Exact) {
        const T direction_scale =
            vector_scale(direction_x, direction_y);
        scale = direction_scale * max_value(
            direction_scale,
            vector_scale(offset_x, offset_y)
        );
    }
    return scaled_sign<Exact>(determinant, scale, eps);
}

template <bool Exact, typename T>
constexpr int dot_sign(
    T ax,
    T ay,
    T bx,
    T by,
    long double eps
) {
    const T value = ax * bx + ay * by;
    T scale = T(0);
    if constexpr (!Exact) {
        scale = vector_scale(ax, ay) * vector_scale(bx, by);
    }
    return scaled_sign<Exact>(value, scale, eps);
}

}  // namespace predicate_detail
}  // namespace geometry
}  // namespace m1une


#line 10 "geometry/point.hpp"

namespace m1une {
namespace geometry {

template <typename T>
concept Coordinate = !std::same_as<std::remove_cv_t<T>, bool> &&
    (std::is_arithmetic_v<T> ||
     (std::copyable<T> && std::totally_ordered<T> && requires(T a, T b) {
         T(0);
         T(1);
         static_cast<long double>(a);
         { +a } -> std::same_as<T>;
         { -a } -> std::same_as<T>;
         { a + b } -> std::same_as<T>;
         { a - b } -> std::same_as<T>;
         { a * b } -> std::same_as<T>;
         { a / b } -> std::same_as<T>;
         { a += b } -> std::same_as<T&>;
         { a -= b } -> std::same_as<T&>;
     }));

// Custom coordinate types keep their own exact arithmetic.
template <typename T>
concept ExactCoordinate = Coordinate<T> && !std::floating_point<T>;

template <Coordinate T>
using wide_type = std::conditional_t<std::integral<T>, __int128_t,
    std::conditional_t<std::floating_point<T>, long double, T>>;

template <Coordinate T>
struct Point {
    T x;
    T y;

    constexpr Point() : x(0), y(0) {}
    constexpr Point(T x_value, T y_value) : x(x_value), y(y_value) {}

    template <Coordinate U>
    explicit constexpr Point(const Point<U>& other)
        : x(static_cast<T>(other.x)), y(static_cast<T>(other.y)) {}

    constexpr Point& operator+=(const Point& other) {
        x += other.x;
        y += other.y;
        return *this;
    }

    constexpr Point& operator-=(const Point& other) {
        x -= other.x;
        y -= other.y;
        return *this;
    }

    constexpr Point operator+() const {
        return *this;
    }

    constexpr Point operator-() const {
        return Point(-x, -y);
    }

    friend constexpr Point operator+(Point left, const Point& right) {
        return left += right;
    }

    friend constexpr Point operator-(Point left, const Point& right) {
        return left -= right;
    }

    friend constexpr bool operator==(const Point&, const Point&) = default;

    friend constexpr bool operator<(const Point& left, const Point& right) {
        if (left.x != right.x) return left.x < right.x;
        return left.y < right.y;
    }
};

template <Coordinate T>
constexpr Point<long double> centroid(const Point<T>& point) {
    return Point<long double>(point);
}

template <Coordinate T, typename Scalar>
requires (std::is_arithmetic_v<Scalar> || Coordinate<Scalar>)
constexpr auto operator*(const Point<T>& point, Scalar scalar) {
    using Result = std::common_type_t<T, Scalar>;
    return Point<Result>(
        Result(point.x) * Result(scalar),
        Result(point.y) * Result(scalar)
    );
}

template <typename Scalar, Coordinate T>
requires (std::is_arithmetic_v<Scalar> || Coordinate<Scalar>)
constexpr auto operator*(Scalar scalar, const Point<T>& point) {
    return point * scalar;
}

template <Coordinate T, typename Scalar>
requires (std::is_arithmetic_v<Scalar> || Coordinate<Scalar>)
constexpr auto operator/(const Point<T>& point, Scalar scalar) {
    using Result = std::common_type_t<T, Scalar>;
    return Point<Result>(
        Result(point.x) / Result(scalar),
        Result(point.y) / Result(scalar)
    );
}

template <Coordinate T>
constexpr wide_type<T> dot(const Point<T>& a, const Point<T>& b) {
    using W = wide_type<T>;
    return W(a.x) * W(b.x) + W(a.y) * W(b.y);
}

template <Coordinate T>
constexpr wide_type<T> cross(const Point<T>& a, const Point<T>& b) {
    using W = wide_type<T>;
    return W(a.x) * W(b.y) - W(a.y) * W(b.x);
}

template <Coordinate T>
constexpr wide_type<T> cross(
    const Point<T>& origin,
    const Point<T>& a,
    const Point<T>& b
) {
    using W = wide_type<T>;
    W ax = W(a.x) - W(origin.x);
    W ay = W(a.y) - W(origin.y);
    W bx = W(b.x) - W(origin.x);
    W by = W(b.y) - W(origin.y);
    return ax * by - ay * bx;
}

template <Coordinate T>
constexpr wide_type<T> norm2(const Point<T>& point) {
    return dot(point, point);
}

template <Coordinate T>
constexpr wide_type<T> distance2(const Point<T>& a, const Point<T>& b) {
    using W = wide_type<T>;
    W dx = W(a.x) - W(b.x);
    W dy = W(a.y) - W(b.y);
    return dx * dx + dy * dy;
}

template <Coordinate T>
long double norm(const Point<T>& point) {
    return std::hypot(
        static_cast<long double>(point.x),
        static_cast<long double>(point.y)
    );
}

template <Coordinate T>
long double distance(const Point<T>& a, const Point<T>& b) {
    return std::hypot(
        static_cast<long double>(a.x) - static_cast<long double>(b.x),
        static_cast<long double>(a.y) - static_cast<long double>(b.y)
    );
}

template <Coordinate T, typename M, typename N>
requires (std::is_arithmetic_v<M> || Coordinate<M>) &&
         (std::is_arithmetic_v<N> || Coordinate<N>)
constexpr Point<long double> internal_division_point(
    const Point<T>& a,
    const Point<T>& b,
    M m,
    N n
) {
    long double first_ratio = static_cast<long double>(m);
    long double second_ratio = static_cast<long double>(n);
    long double denominator = first_ratio + second_ratio;
    assert(denominator != 0);
    Point<long double> first(a);
    Point<long double> direction = Point<long double>(b) - first;
    return first + direction * (first_ratio / denominator);
}

template <Coordinate T, typename M, typename N>
requires (std::is_arithmetic_v<M> || Coordinate<M>) &&
         (std::is_arithmetic_v<N> || Coordinate<N>)
constexpr Point<long double> external_division_point(
    const Point<T>& a,
    const Point<T>& b,
    M m,
    N n
) {
    long double first_ratio = static_cast<long double>(m);
    long double second_ratio = static_cast<long double>(n);
    long double denominator = first_ratio - second_ratio;
    assert(denominator != 0);
    Point<long double> first(a);
    Point<long double> direction = Point<long double>(b) - first;
    return first + direction * (first_ratio / denominator);
}

template <Coordinate T>
constexpr int sign(wide_type<T> value, long double eps = 1e-12L) {
    return predicate_detail::scaled_sign<ExactCoordinate<T>>(
        value,
        wide_type<T>(1),
        eps
    );
}

template <Coordinate T>
constexpr int orientation(
    const Point<T>& a,
    const Point<T>& b,
    const Point<T>& c,
    long double eps = 1e-12L
) {
    using W = wide_type<T>;
    const W first_x = W(b.x) - W(a.x);
    const W first_y = W(b.y) - W(a.y);
    const W second_x = W(c.x) - W(a.x);
    const W second_y = W(c.y) - W(a.y);
    return predicate_detail::orientation_sign<ExactCoordinate<T>>(
        first_x,
        first_y,
        second_x,
        second_y,
        eps
    );
}

template <Coordinate T>
constexpr bool collinear(
    const Point<T>& a,
    const Point<T>& b,
    const Point<T>& c,
    long double eps = 1e-12L
) {
    return orientation(a, b, c, eps) == 0;
}

template <Coordinate T>
Point<long double> rotate(const Point<T>& point, long double angle) {
    long double cosine = std::cos(angle);
    long double sine = std::sin(angle);
    return Point<long double>(
        static_cast<long double>(point.x) * cosine -
            static_cast<long double>(point.y) * sine,
        static_cast<long double>(point.x) * sine +
            static_cast<long double>(point.y) * cosine
    );
}

template <Coordinate T>
Point<long double> normalized(const Point<T>& point) {
    long double length = norm(point);
    assert(length != 0);
    return Point<long double>(
        static_cast<long double>(point.x) / length,
        static_cast<long double>(point.y) / length
    );
}

}  // namespace geometry
}  // namespace m1une


#line 9 "geometry/linear.hpp"

namespace m1une {
namespace geometry {

template <Coordinate T>
struct Line {
    Point<T> a;
    Point<T> b;
};

template <Coordinate T>
struct Segment {
    Point<T> a;
    Point<T> b;
};

template <Coordinate T>
struct Ray {
    Point<T> origin;
    Point<T> through;
};

enum class LinearIntersectionKind {
    Empty,
    Point,
    Segment,
    Ray,
    Line,
};

struct LinearIntersection {
    LinearIntersectionKind kind;
    Point<long double> first;
    Point<long double> second;
};

struct ClosestPoints {
    Point<long double> first;
    Point<long double> second;
};

namespace linear_intersection_detail {

inline LinearIntersection make_empty() {
    const Point<long double> zero;
    return LinearIntersection{
        LinearIntersectionKind::Empty,
        zero,
        zero,
    };
}

template <Coordinate T>
LinearIntersection make_point(const Point<T>& point) {
    const Point<long double> converted(point);
    return LinearIntersection{
        LinearIntersectionKind::Point,
        converted,
        converted,
    };
}

template <Coordinate T>
LinearIntersection make_object(
    LinearIntersectionKind kind,
    const Point<T>& first,
    const Point<T>& second
) {
    return LinearIntersection{
        kind,
        Point<long double>(first),
        Point<long double>(second),
    };
}

}  // namespace linear_intersection_detail

template <Coordinate T>
constexpr Point<long double> centroid(const Segment<T>& segment) {
    return Point<long double>(
        (
            static_cast<long double>(segment.a.x) +
            static_cast<long double>(segment.b.x)
        ) / 2,
        (
            static_cast<long double>(segment.a.y) +
            static_cast<long double>(segment.b.y)
        ) / 2
    );
}

template <Coordinate T>
bool on_line(
    const Line<T>& line,
    const Point<T>& point,
    long double eps = 1e-12L
) {
    assert(line.a != line.b);
    return orientation(line.a, line.b, point, eps) == 0;
}

template <Coordinate T>
bool parallel(const Line<T>& first, const Line<T>& second, long double eps = 1e-12L) {
    using W = wide_type<T>;
    W first_x = W(first.b.x) - W(first.a.x);
    W first_y = W(first.b.y) - W(first.a.y);
    W second_x = W(second.b.x) - W(second.a.x);
    W second_y = W(second.b.y) - W(second.a.y);
    return predicate_detail::determinant_sign<ExactCoordinate<T>>(
        first_x,
        first_y,
        second_x,
        second_y,
        eps
    ) == 0;
}

template <Coordinate T>
bool orthogonal(const Line<T>& first, const Line<T>& second, long double eps = 1e-12L) {
    using W = wide_type<T>;
    W first_x = W(first.b.x) - W(first.a.x);
    W first_y = W(first.b.y) - W(first.a.y);
    W second_x = W(second.b.x) - W(second.a.x);
    W second_y = W(second.b.y) - W(second.a.y);
    return predicate_detail::dot_sign<ExactCoordinate<T>>(
        first_x,
        first_y,
        second_x,
        second_y,
        eps
    ) == 0;
}

template <Coordinate T>
Point<long double> projection(const Line<T>& line, const Point<T>& point) {
    assert(line.a != line.b);
    Point<long double> a(line.a);
    Point<long double> direction(
        static_cast<long double>(line.b.x) - static_cast<long double>(line.a.x),
        static_cast<long double>(line.b.y) - static_cast<long double>(line.a.y)
    );
    Point<long double> offset(
        static_cast<long double>(point.x) - a.x,
        static_cast<long double>(point.y) - a.y
    );
    long double ratio = dot(offset, direction) / dot(direction, direction);
    return a + direction * ratio;
}

template <Coordinate T>
Point<long double> reflection(const Line<T>& line, const Point<T>& point) {
    Point<long double> projected = projection(line, point);
    return projected * 2.0L - Point<long double>(point);
}

template <Coordinate T>
bool intersects(
    const Line<T>& first,
    const Line<T>& second,
    long double eps = 1e-12L
) {
    return !parallel(first, second, eps) || on_line(first, second.a, eps);
}

template <Coordinate T>
bool on_segment(
    const Segment<T>& segment,
    const Point<T>& point,
    long double eps = 1e-12L
) {
    if (orientation(segment.a, segment.b, point, eps) != 0) return false;
    using W = wide_type<T>;
    const W direction_x = W(segment.b.x) - W(segment.a.x);
    const W direction_y = W(segment.b.y) - W(segment.a.y);
    if (direction_x == W(0) && direction_y == W(0)) {
        if constexpr (ExactCoordinate<T>) {
            return point == segment.a;
        } else {
            return
                predicate_detail::absolute(W(point.x) - W(segment.a.x)) <= eps &&
                predicate_detail::absolute(W(point.y) - W(segment.a.y)) <= eps;
        }
    }
    const W offset_x = W(point.x) - W(segment.a.x);
    const W offset_y = W(point.y) - W(segment.a.y);
    const W projection =
        offset_x * direction_x + offset_y * direction_y;
    const W length_squared =
        direction_x * direction_x + direction_y * direction_y;
    return
        predicate_detail::scaled_sign<ExactCoordinate<T>>(
            projection,
            length_squared,
            eps
        ) >= 0 &&
        predicate_detail::scaled_sign<ExactCoordinate<T>>(
            projection - length_squared,
            length_squared,
            eps
        ) <= 0;
}

template <Coordinate T>
Point<long double> projection(
    const Segment<T>& segment,
    const Point<T>& point
) {
    const Point<long double> first(segment.a);
    const Point<long double> direction =
        Point<long double>(segment.b) - first;
    const long double length_squared = dot(direction, direction);
    if (length_squared == 0) return first;
    const long double ratio = std::clamp(
        dot(Point<long double>(point) - first, direction) / length_squared,
        0.0L,
        1.0L
    );
    return first + direction * ratio;
}

template <Coordinate T>
bool intersects(
    const Segment<T>& first,
    const Segment<T>& second,
    long double eps = 1e-12L
) {
    int abc = orientation(first.a, first.b, second.a, eps);
    int abd = orientation(first.a, first.b, second.b, eps);
    int cda = orientation(second.a, second.b, first.a, eps);
    int cdb = orientation(second.a, second.b, first.b, eps);

    if (abc == 0 && on_segment(first, second.a, eps)) return true;
    if (abd == 0 && on_segment(first, second.b, eps)) return true;
    if (cda == 0 && on_segment(second, first.a, eps)) return true;
    if (cdb == 0 && on_segment(second, first.b, eps)) return true;
    return abc * abd < 0 && cda * cdb < 0;
}

template <Coordinate T>
bool intersects(
    const Line<T>& line,
    const Segment<T>& segment,
    long double eps = 1e-12L
) {
    int first_side = orientation(line.a, line.b, segment.a, eps);
    int second_side = orientation(line.a, line.b, segment.b, eps);
    return first_side == 0 || second_side == 0 || first_side != second_side;
}

template <Coordinate T>
bool intersects(
    const Segment<T>& segment,
    const Line<T>& line,
    long double eps = 1e-12L
) {
    return intersects(line, segment, eps);
}

namespace linear_parameter_detail {

template <Coordinate T>
struct Parameters {
    wide_type<T> denominator;
    wide_type<T> denominator_scale;
    wide_type<T> first_numerator;
    wide_type<T> second_numerator;
};

template <Coordinate T>
Parameters<T> parameters(
    const Point<T>& first_origin,
    const Point<T>& first_through,
    const Point<T>& second_origin,
    const Point<T>& second_through
) {
    using W = wide_type<T>;
    W first_x = W(first_through.x) - W(first_origin.x);
    W first_y = W(first_through.y) - W(first_origin.y);
    W second_x = W(second_through.x) - W(second_origin.x);
    W second_y = W(second_through.y) - W(second_origin.y);
    W offset_x = W(second_origin.x) - W(first_origin.x);
    W offset_y = W(second_origin.y) - W(first_origin.y);
    return Parameters<T>{
        first_x * second_y - first_y * second_x,
        predicate_detail::determinant_scale<ExactCoordinate<T>>(
            first_x,
            first_y,
            second_x,
            second_y
        ),
        offset_x * second_y - offset_y * second_x,
        offset_x * first_y - offset_y * first_x
    };
}

template <Coordinate T>
int denominator_sign(const Parameters<T>& values, long double eps) {
    return predicate_detail::scaled_sign<ExactCoordinate<T>>(
        values.denominator,
        values.denominator_scale,
        eps
    );
}

template <Coordinate T>
bool ratio_nonnegative(
    wide_type<T> numerator,
    wide_type<T> denominator,
    long double eps
) {
    const int numerator_sign =
        predicate_detail::scaled_sign<ExactCoordinate<T>>(
            numerator,
            predicate_detail::absolute(denominator),
            eps
        );
    const int denominator_direction =
        (denominator > 0) - (denominator < 0);
    return
        numerator_sign == 0 ||
        numerator_sign == denominator_direction;
}

template <Coordinate T>
bool ratio_in_unit_interval(
    wide_type<T> numerator,
    wide_type<T> denominator,
    long double eps
) {
    const auto scale = predicate_detail::absolute(denominator);
    const int start_sign =
        predicate_detail::scaled_sign<ExactCoordinate<T>>(
            numerator,
            scale,
            eps
        );
    const int finish_sign =
        predicate_detail::scaled_sign<ExactCoordinate<T>>(
            numerator - denominator,
            scale,
            eps
        );
    if (denominator > 0) {
        return start_sign >= 0 && finish_sign <= 0;
    }
    return start_sign <= 0 && finish_sign >= 0;
}

}  // namespace linear_parameter_detail

template <Coordinate T>
bool on_ray(
    const Ray<T>& ray,
    const Point<T>& point,
    long double eps = 1e-12L
) {
    assert(ray.origin != ray.through);
    if (orientation(ray.origin, ray.through, point, eps) != 0) return false;
    using W = wide_type<T>;
    W direction_x = W(ray.through.x) - W(ray.origin.x);
    W direction_y = W(ray.through.y) - W(ray.origin.y);
    W offset_x = W(point.x) - W(ray.origin.x);
    W offset_y = W(point.y) - W(ray.origin.y);
    const W projection =
        direction_x * offset_x + direction_y * offset_y;
    const W length_squared =
        direction_x * direction_x + direction_y * direction_y;
    return predicate_detail::scaled_sign<ExactCoordinate<T>>(
        projection,
        length_squared,
        eps
    ) >= 0;
}

template <Coordinate T>
Point<long double> projection(const Ray<T>& ray, const Point<T>& point) {
    assert(ray.origin != ray.through);
    Point<long double> origin(ray.origin);
    Point<long double> direction =
        Point<long double>(ray.through) - origin;
    Point<long double> offset = Point<long double>(point) - origin;
    long double ratio = dot(offset, direction) / dot(direction, direction);
    if (ratio < 0) ratio = 0;
    return origin + direction * ratio;
}

template <Coordinate T>
Ray<long double> reflection(const Line<T>& line, const Ray<T>& ray) {
    assert(ray.origin != ray.through);
    return Ray<long double>{
        reflection(line, ray.origin),
        reflection(line, ray.through)
    };
}

template <Coordinate T>
Ray<long double> reflected_ray(
    const Ray<T>& incoming,
    const Point<T>& hit,
    const Line<T>& mirror,
    long double eps = 1e-12L
) {
    assert(incoming.origin != incoming.through);
    assert(on_line(mirror, hit, eps));
    Point<T> translated = hit + (incoming.through - incoming.origin);
    return Ray<long double>{
        Point<long double>(hit),
        reflection(mirror, translated)
    };
}

template <Coordinate T>
bool intersects(
    const Ray<T>& ray,
    const Line<T>& line,
    long double eps = 1e-12L
) {
    assert(ray.origin != ray.through);
    assert(line.a != line.b);
    linear_parameter_detail::Parameters<T> values =
        linear_parameter_detail::parameters(
        ray.origin,
        ray.through,
        line.a,
        line.b
    );
    if (linear_parameter_detail::denominator_sign(values, eps) == 0) {
        return on_line(line, ray.origin, eps);
    }
    return linear_parameter_detail::ratio_nonnegative<T>(
        values.first_numerator,
        values.denominator,
        eps
    );
}

template <Coordinate T>
bool intersects(
    const Line<T>& line,
    const Ray<T>& ray,
    long double eps = 1e-12L
) {
    return intersects(ray, line, eps);
}

template <Coordinate T>
bool intersects(
    const Ray<T>& ray,
    const Segment<T>& segment,
    long double eps = 1e-12L
) {
    assert(ray.origin != ray.through);
    if (segment.a == segment.b) return on_ray(ray, segment.a, eps);

    linear_parameter_detail::Parameters<T> values =
        linear_parameter_detail::parameters(
        ray.origin,
        ray.through,
        segment.a,
        segment.b
    );
    if (linear_parameter_detail::denominator_sign(values, eps) == 0) {
        if (orientation(ray.origin, ray.through, segment.a, eps) != 0) {
            return false;
        }
        return on_ray(ray, segment.a, eps) ||
               on_ray(ray, segment.b, eps) ||
               on_segment(segment, ray.origin, eps);
    }
    return linear_parameter_detail::ratio_nonnegative<T>(
               values.first_numerator,
               values.denominator,
               eps
           ) &&
           linear_parameter_detail::ratio_in_unit_interval<T>(
               values.second_numerator,
               values.denominator,
               eps
           );
}

template <Coordinate T>
bool intersects(
    const Segment<T>& segment,
    const Ray<T>& ray,
    long double eps = 1e-12L
) {
    return intersects(ray, segment, eps);
}

template <Coordinate T>
bool intersects(
    const Ray<T>& first,
    const Ray<T>& second,
    long double eps = 1e-12L
) {
    assert(first.origin != first.through);
    assert(second.origin != second.through);
    linear_parameter_detail::Parameters<T> values =
        linear_parameter_detail::parameters(
        first.origin,
        first.through,
        second.origin,
        second.through
    );
    if (linear_parameter_detail::denominator_sign(values, eps) == 0) {
        if (orientation(first.origin, first.through, second.origin, eps) != 0) {
            return false;
        }
        return on_ray(first, second.origin, eps) ||
               on_ray(second, first.origin, eps);
    }
    return linear_parameter_detail::ratio_nonnegative<T>(
               values.first_numerator,
               values.denominator,
               eps
           ) &&
           linear_parameter_detail::ratio_nonnegative<T>(
               values.second_numerator,
               values.denominator,
               eps
           );
}

namespace linear_intersection_detail {

enum class Domain {
    Line,
    Segment,
    Ray,
};

template <Coordinate T>
struct ParametricObject {
    Point<T> origin;
    Point<T> through;
    Domain domain;
};

template <Coordinate T>
ParametricObject<T> parametric_object(const Line<T>& line) {
    assert(line.a != line.b);
    return ParametricObject<T>{line.a, line.b, Domain::Line};
}

template <Coordinate T>
ParametricObject<T> parametric_object(const Segment<T>& segment) {
    return ParametricObject<T>{segment.a, segment.b, Domain::Segment};
}

template <Coordinate T>
ParametricObject<T> parametric_object(const Ray<T>& ray) {
    assert(ray.origin != ray.through);
    return ParametricObject<T>{ray.origin, ray.through, Domain::Ray};
}

template <Coordinate T>
bool contains(
    const ParametricObject<T>& object,
    const Point<T>& point,
    long double eps
) {
    if (object.domain == Domain::Line) {
        return on_line(Line<T>{object.origin, object.through}, point, eps);
    }
    if (object.domain == Domain::Segment) {
        return on_segment(
            Segment<T>{object.origin, object.through},
            point,
            eps
        );
    }
    return on_ray(Ray<T>{object.origin, object.through}, point, eps);
}

template <Coordinate T>
bool accepts_parameter(
    Domain domain,
    wide_type<T> numerator,
    wide_type<T> denominator,
    long double eps
) {
    if (domain == Domain::Line) return true;
    if (domain == Domain::Ray) {
        return linear_parameter_detail::ratio_nonnegative<T>(
            numerator,
            denominator,
            eps
        );
    }
    return linear_parameter_detail::ratio_in_unit_interval<T>(
        numerator,
        denominator,
        eps
    );
}

template <Coordinate T>
Point<long double> point_at_ratio(
    const ParametricObject<T>& object,
    wide_type<T> numerator,
    wide_type<T> denominator
) {
    const long double ratio =
        static_cast<long double>(numerator) /
        static_cast<long double>(denominator);
    const Point<long double> origin(object.origin);
    const Point<long double> direction =
        Point<long double>(object.through) - origin;
    return origin + direction * ratio;
}

template <Coordinate T>
struct AxisProjection {
    bool use_x;
    bool negate;

    wide_type<T> operator()(const Point<T>& point) const {
        const wide_type<T> value = use_x
            ? wide_type<T>(point.x)
            : wide_type<T>(point.y);
        return negate ? -value : value;
    }
};

template <Coordinate T>
AxisProjection<T> axis_projection(const ParametricObject<T>& object) {
    using W = wide_type<T>;
    const W direction_x = W(object.through.x) - W(object.origin.x);
    const W direction_y = W(object.through.y) - W(object.origin.y);
    const bool use_x =
        predicate_detail::absolute(direction_x) >=
        predicate_detail::absolute(direction_y);
    const W component = use_x ? direction_x : direction_y;
    assert(component != W(0));
    return AxisProjection<T>{use_x, component < W(0)};
}

template <Coordinate T>
struct ParameterInterval {
    bool has_lower;
    bool has_upper;
    wide_type<T> lower;
    wide_type<T> upper;
};

template <Coordinate T>
ParameterInterval<T> parameter_interval(
    const ParametricObject<T>& object,
    const AxisProjection<T>& projection
) {
    using W = wide_type<T>;
    const W origin = projection(object.origin);
    const W through = projection(object.through);
    if (object.domain == Domain::Line) {
        return ParameterInterval<T>{false, false, W(0), W(0)};
    }
    if (object.domain == Domain::Segment) {
        return ParameterInterval<T>{
            true,
            true,
            std::min(origin, through),
            std::max(origin, through),
        };
    }
    if (origin < through) {
        return ParameterInterval<T>{true, false, origin, W(0)};
    }
    return ParameterInterval<T>{false, true, W(0), origin};
}

template <Coordinate T>
ParameterInterval<T> intersect_intervals(
    ParameterInterval<T> first,
    const ParameterInterval<T>& second
) {
    if (
        second.has_lower &&
        (!first.has_lower || first.lower < second.lower)
    ) {
        first.has_lower = true;
        first.lower = second.lower;
    }
    if (
        second.has_upper &&
        (!first.has_upper || second.upper < first.upper)
    ) {
        first.has_upper = true;
        first.upper = second.upper;
    }
    return first;
}

template <Coordinate T>
Point<long double> point_at_projection(
    const ParametricObject<T>& object,
    const AxisProjection<T>& projection,
    long double target
) {
    const long double origin =
        static_cast<long double>(projection(object.origin));
    const long double through =
        static_cast<long double>(projection(object.through));
    const long double ratio = (target - origin) / (through - origin);
    const Point<long double> point(object.origin);
    const Point<long double> direction =
        Point<long double>(object.through) - point;
    return point + direction * ratio;
}

template <Coordinate T>
LinearIntersection collinear_intersection(
    const ParametricObject<T>& first,
    const ParametricObject<T>& second,
    long double eps
) {
    using W = wide_type<T>;
    const AxisProjection<T> projection = axis_projection(first);
    const ParameterInterval<T> first_interval =
        parameter_interval(first, projection);
    const ParameterInterval<T> second_interval =
        parameter_interval(second, projection);
    const ParameterInterval<T> common =
        intersect_intervals(first_interval, second_interval);

    W scale = predicate_detail::absolute(
        projection(first.through) - projection(first.origin)
    );
    scale = std::max(
        scale,
        predicate_detail::absolute(
            projection(second.through) - projection(second.origin)
        )
    );

    if (common.has_lower && common.has_upper) {
        const int order = predicate_detail::scaled_sign<ExactCoordinate<T>>(
            common.lower - common.upper,
            scale,
            eps
        );
        if (order > 0) return make_empty();
        if (order == 0) {
            const long double coordinate =
                (
                    static_cast<long double>(common.lower) +
                    static_cast<long double>(common.upper)
                ) / 2.0L;
            return make_point(
                point_at_projection(first, projection, coordinate)
            );
        }
        return make_object(
            LinearIntersectionKind::Segment,
            point_at_projection(
                first,
                projection,
                static_cast<long double>(common.lower)
            ),
            point_at_projection(
                first,
                projection,
                static_cast<long double>(common.upper)
            )
        );
    }

    const Point<long double> direction =
        Point<long double>(first.through) -
        Point<long double>(first.origin);
    if (common.has_lower) {
        const Point<long double> origin = point_at_projection(
            first,
            projection,
            static_cast<long double>(common.lower)
        );
        return make_object(
            LinearIntersectionKind::Ray,
            origin,
            origin + direction
        );
    }
    if (common.has_upper) {
        const Point<long double> origin = point_at_projection(
            first,
            projection,
            static_cast<long double>(common.upper)
        );
        return make_object(
            LinearIntersectionKind::Ray,
            origin,
            origin - direction
        );
    }
    return make_object(
        LinearIntersectionKind::Line,
        first.origin,
        first.through
    );
}

template <Coordinate T>
LinearIntersection intersect(
    const ParametricObject<T>& first,
    const ParametricObject<T>& second,
    long double eps
) {
    const bool first_degenerate = first.origin == first.through;
    const bool second_degenerate = second.origin == second.through;
    if (first_degenerate) {
        assert(first.domain == Domain::Segment);
        if (contains(second, first.origin, eps)) {
            return make_point(first.origin);
        }
        return make_empty();
    }
    if (second_degenerate) {
        assert(second.domain == Domain::Segment);
        if (contains(first, second.origin, eps)) {
            return make_point(second.origin);
        }
        return make_empty();
    }

    const linear_parameter_detail::Parameters<T> values =
        linear_parameter_detail::parameters(
        first.origin,
        first.through,
        second.origin,
        second.through
    );
    if (linear_parameter_detail::denominator_sign(values, eps) != 0) {
        if (
            !accepts_parameter<T>(
                first.domain,
                values.first_numerator,
                values.denominator,
                eps
            ) ||
            !accepts_parameter<T>(
                second.domain,
                values.second_numerator,
                values.denominator,
                eps
            )
        ) {
            return make_empty();
        }
        return make_point(
            point_at_ratio(
                first,
                values.first_numerator,
                values.denominator
            )
        );
    }
    if (
        orientation(
            first.origin,
            first.through,
            second.origin,
            eps
        ) != 0
    ) {
        return make_empty();
    }
    return collinear_intersection(first, second, eps);
}

}  // namespace linear_intersection_detail

template <Coordinate T>
LinearIntersection linear_intersection(
    const Line<T>& first,
    const Line<T>& second,
    long double eps = 1e-12L
) {
    return linear_intersection_detail::intersect(
        linear_intersection_detail::parametric_object(first),
        linear_intersection_detail::parametric_object(second),
        eps
    );
}

template <Coordinate T>
LinearIntersection linear_intersection(
    const Line<T>& line,
    const Segment<T>& segment,
    long double eps = 1e-12L
) {
    return linear_intersection_detail::intersect(
        linear_intersection_detail::parametric_object(line),
        linear_intersection_detail::parametric_object(segment),
        eps
    );
}

template <Coordinate T>
LinearIntersection linear_intersection(
    const Segment<T>& segment,
    const Line<T>& line,
    long double eps = 1e-12L
) {
    return linear_intersection_detail::intersect(
        linear_intersection_detail::parametric_object(segment),
        linear_intersection_detail::parametric_object(line),
        eps
    );
}

template <Coordinate T>
LinearIntersection linear_intersection(
    const Segment<T>& first,
    const Segment<T>& second,
    long double eps = 1e-12L
) {
    return linear_intersection_detail::intersect(
        linear_intersection_detail::parametric_object(first),
        linear_intersection_detail::parametric_object(second),
        eps
    );
}

template <Coordinate T>
LinearIntersection linear_intersection(
    const Ray<T>& ray,
    const Line<T>& line,
    long double eps = 1e-12L
) {
    return linear_intersection_detail::intersect(
        linear_intersection_detail::parametric_object(ray),
        linear_intersection_detail::parametric_object(line),
        eps
    );
}

template <Coordinate T>
LinearIntersection linear_intersection(
    const Line<T>& line,
    const Ray<T>& ray,
    long double eps = 1e-12L
) {
    return linear_intersection_detail::intersect(
        linear_intersection_detail::parametric_object(line),
        linear_intersection_detail::parametric_object(ray),
        eps
    );
}

template <Coordinate T>
LinearIntersection linear_intersection(
    const Ray<T>& ray,
    const Segment<T>& segment,
    long double eps = 1e-12L
) {
    return linear_intersection_detail::intersect(
        linear_intersection_detail::parametric_object(ray),
        linear_intersection_detail::parametric_object(segment),
        eps
    );
}

template <Coordinate T>
LinearIntersection linear_intersection(
    const Segment<T>& segment,
    const Ray<T>& ray,
    long double eps = 1e-12L
) {
    return linear_intersection_detail::intersect(
        linear_intersection_detail::parametric_object(segment),
        linear_intersection_detail::parametric_object(ray),
        eps
    );
}

template <Coordinate T>
LinearIntersection linear_intersection(
    const Ray<T>& first,
    const Ray<T>& second,
    long double eps = 1e-12L
) {
    return linear_intersection_detail::intersect(
        linear_intersection_detail::parametric_object(first),
        linear_intersection_detail::parametric_object(second),
        eps
    );
}

namespace closest_points_detail {

inline ClosestPoints reversed(const ClosestPoints& result) {
    return ClosestPoints{result.second, result.first};
}

inline bool point_less(
    const Point<long double>& first,
    const Point<long double>& second
) {
    if (first.x != second.x) return first.x < second.x;
    return first.y < second.y;
}

inline ClosestPoints common_point(const LinearIntersection& intersection) {
    assert(intersection.kind != LinearIntersectionKind::Empty);
    Point<long double> point = intersection.first;
    if (intersection.kind == LinearIntersectionKind::Segment) {
        if (point_less(intersection.second, point)) {
            point = intersection.second;
        }
    } else if (intersection.kind == LinearIntersectionKind::Line) {
        const Line<long double> line{
            intersection.first,
            intersection.second
        };
        point = projection(line, Point<long double>(0, 0));
    }
    return ClosestPoints{point, point};
}

inline long double separation2(const ClosestPoints& result) {
    return distance2(result.first, result.second);
}

inline bool canonical_less(
    const ClosestPoints& first,
    const ClosestPoints& second
) {
    Point<long double> first_start = first.first;
    Point<long double> first_finish = first.second;
    if (point_less(first_finish, first_start)) {
        std::swap(first_start, first_finish);
    }
    Point<long double> second_start = second.first;
    Point<long double> second_finish = second.second;
    if (point_less(second_finish, second_start)) {
        std::swap(second_start, second_finish);
    }
    if (point_less(first_start, second_start)) return true;
    if (point_less(second_start, first_start)) return false;
    return point_less(first_finish, second_finish);
}

inline void consider(ClosestPoints& best, const ClosestPoints& candidate) {
    const long double best_distance = separation2(best);
    const long double candidate_distance = separation2(candidate);
    if (
        candidate_distance < best_distance ||
        (
            candidate_distance == best_distance &&
            canonical_less(candidate, best)
        )
    ) {
        best = candidate;
    }
}

}  // namespace closest_points_detail

template <Coordinate T>
ClosestPoints closest_points(
    const Point<T>& first,
    const Point<T>& second
) {
    return ClosestPoints{
        Point<long double>(first),
        Point<long double>(second),
    };
}

template <Coordinate T>
ClosestPoints closest_points(
    const Line<T>& line,
    const Point<T>& point
) {
    return ClosestPoints{
        projection(line, point),
        Point<long double>(point),
    };
}

template <Coordinate T>
ClosestPoints closest_points(
    const Point<T>& point,
    const Line<T>& line
) {
    return closest_points_detail::reversed(closest_points(line, point));
}

template <Coordinate T>
ClosestPoints closest_points(
    const Segment<T>& segment,
    const Point<T>& point
) {
    return ClosestPoints{
        projection(segment, point),
        Point<long double>(point),
    };
}

template <Coordinate T>
ClosestPoints closest_points(
    const Point<T>& point,
    const Segment<T>& segment
) {
    return closest_points_detail::reversed(closest_points(segment, point));
}

template <Coordinate T>
ClosestPoints closest_points(
    const Ray<T>& ray,
    const Point<T>& point
) {
    return ClosestPoints{
        projection(ray, point),
        Point<long double>(point),
    };
}

template <Coordinate T>
ClosestPoints closest_points(
    const Point<T>& point,
    const Ray<T>& ray
) {
    return closest_points_detail::reversed(closest_points(ray, point));
}

template <Coordinate T>
ClosestPoints closest_points(
    const Line<T>& first,
    const Line<T>& second,
    long double eps = 1e-12L
) {
    const LinearIntersection intersection =
        linear_intersection(first, second, eps);
    if (intersection.kind != LinearIntersectionKind::Empty) {
        return closest_points_detail::common_point(intersection);
    }
    ClosestPoints result = closest_points(first, second.a);
    closest_points_detail::consider(
        result,
        closest_points(first.a, second)
    );
    return result;
}

template <Coordinate T>
ClosestPoints closest_points(
    const Line<T>& line,
    const Segment<T>& segment,
    long double eps = 1e-12L
) {
    const LinearIntersection intersection =
        linear_intersection(line, segment, eps);
    if (intersection.kind != LinearIntersectionKind::Empty) {
        return closest_points_detail::common_point(intersection);
    }
    ClosestPoints result = closest_points(line, segment.a);
    closest_points_detail::consider(
        result,
        closest_points(line, segment.b)
    );
    return result;
}

template <Coordinate T>
ClosestPoints closest_points(
    const Segment<T>& segment,
    const Line<T>& line,
    long double eps = 1e-12L
) {
    return closest_points_detail::reversed(
        closest_points(line, segment, eps)
    );
}

template <Coordinate T>
ClosestPoints closest_points(
    const Segment<T>& first,
    const Segment<T>& second,
    long double eps = 1e-12L
) {
    const LinearIntersection intersection =
        linear_intersection(first, second, eps);
    if (intersection.kind != LinearIntersectionKind::Empty) {
        return closest_points_detail::common_point(intersection);
    }
    ClosestPoints result = closest_points(first, second.a);
    closest_points_detail::consider(
        result,
        closest_points(first, second.b)
    );
    closest_points_detail::consider(
        result,
        closest_points(first.a, second)
    );
    closest_points_detail::consider(
        result,
        closest_points(first.b, second)
    );
    return result;
}

template <Coordinate T>
ClosestPoints closest_points(
    const Line<T>& line,
    const Ray<T>& ray,
    long double eps = 1e-12L
) {
    const LinearIntersection intersection =
        linear_intersection(line, ray, eps);
    if (intersection.kind != LinearIntersectionKind::Empty) {
        return closest_points_detail::common_point(intersection);
    }
    return closest_points(line, ray.origin);
}

template <Coordinate T>
ClosestPoints closest_points(
    const Ray<T>& ray,
    const Line<T>& line,
    long double eps = 1e-12L
) {
    return closest_points_detail::reversed(closest_points(line, ray, eps));
}

template <Coordinate T>
ClosestPoints closest_points(
    const Ray<T>& ray,
    const Segment<T>& segment,
    long double eps = 1e-12L
) {
    const LinearIntersection intersection =
        linear_intersection(ray, segment, eps);
    if (intersection.kind != LinearIntersectionKind::Empty) {
        return closest_points_detail::common_point(intersection);
    }
    ClosestPoints result = closest_points(ray, segment.a);
    closest_points_detail::consider(
        result,
        closest_points(ray, segment.b)
    );
    closest_points_detail::consider(
        result,
        closest_points(ray.origin, segment)
    );
    return result;
}

template <Coordinate T>
ClosestPoints closest_points(
    const Segment<T>& segment,
    const Ray<T>& ray,
    long double eps = 1e-12L
) {
    return closest_points_detail::reversed(
        closest_points(ray, segment, eps)
    );
}

template <Coordinate T>
ClosestPoints closest_points(
    const Ray<T>& first,
    const Ray<T>& second,
    long double eps = 1e-12L
) {
    const LinearIntersection intersection =
        linear_intersection(first, second, eps);
    if (intersection.kind != LinearIntersectionKind::Empty) {
        return closest_points_detail::common_point(intersection);
    }
    ClosestPoints result = closest_points(first, second.origin);
    closest_points_detail::consider(
        result,
        closest_points(first.origin, second)
    );
    return result;
}

template <Coordinate T>
long double distance(const Line<T>& line, const Point<T>& point) {
    const ClosestPoints result = closest_points(line, point);
    return geometry::distance(result.first, result.second);
}

template <Coordinate T>
long double distance(const Point<T>& point, const Line<T>& line) {
    return distance(line, point);
}

template <Coordinate T>
long double distance(const Segment<T>& segment, const Point<T>& point) {
    const ClosestPoints result = closest_points(segment, point);
    return geometry::distance(result.first, result.second);
}

template <Coordinate T>
long double distance(const Point<T>& point, const Segment<T>& segment) {
    return distance(segment, point);
}

template <Coordinate T>
long double distance(const Ray<T>& ray, const Point<T>& point) {
    const ClosestPoints result = closest_points(ray, point);
    return geometry::distance(result.first, result.second);
}

template <Coordinate T>
long double distance(const Point<T>& point, const Ray<T>& ray) {
    return distance(ray, point);
}

template <Coordinate T>
long double distance(const Line<T>& first, const Line<T>& second) {
    const ClosestPoints result = closest_points(first, second);
    return geometry::distance(result.first, result.second);
}

template <Coordinate T>
long double distance(const Line<T>& line, const Segment<T>& segment) {
    const ClosestPoints result = closest_points(line, segment);
    return geometry::distance(result.first, result.second);
}

template <Coordinate T>
long double distance(const Segment<T>& segment, const Line<T>& line) {
    return distance(line, segment);
}

template <Coordinate T>
long double distance(const Segment<T>& first, const Segment<T>& second) {
    const ClosestPoints result = closest_points(first, second);
    return geometry::distance(result.first, result.second);
}

template <Coordinate T>
long double distance(const Line<T>& line, const Ray<T>& ray) {
    const ClosestPoints result = closest_points(line, ray);
    return geometry::distance(result.first, result.second);
}

template <Coordinate T>
long double distance(const Ray<T>& ray, const Line<T>& line) {
    return distance(line, ray);
}

template <Coordinate T>
long double distance(const Ray<T>& ray, const Segment<T>& segment) {
    const ClosestPoints result = closest_points(ray, segment);
    return geometry::distance(result.first, result.second);
}

template <Coordinate T>
long double distance(const Segment<T>& segment, const Ray<T>& ray) {
    return distance(ray, segment);
}

template <Coordinate T>
long double distance(const Ray<T>& first, const Ray<T>& second) {
    const ClosestPoints result = closest_points(first, second);
    return geometry::distance(result.first, result.second);
}

}  // namespace geometry
}  // namespace m1une


#line 15 "geometry/circle.hpp"

namespace m1une {
namespace geometry {

template <Coordinate T>
struct Circle {
    Point<T> center;
    T radius;
    bool filled = true;
};

enum class PointInCircle {
    Outside = 0,
    Boundary = 1,
    Inside = 2,
};

enum class CircleRelation {
    Separate,
    ExternallyTangent,
    Intersecting,
    InternallyTangent,
    Contained,
    Coincident,
};

enum class AngularCoverageKind {
    Empty,
    Point,
    Arc,
    Full,
};

struct AngularCoverage {
    AngularCoverageKind kind = AngularCoverageKind::Empty;
    long double begin = 0.0L;
    long double end = 0.0L;
};

struct CircleContact {
    Point<long double> point;
    long double first_argument = 0.0L;
    long double second_argument = 0.0L;
};

enum class CircleContactKind {
    Empty,
    Point,
    TwoPoints,
    Coincident,
};

struct CircleCircleIntersection {
    CircleRelation relation = CircleRelation::Separate;
    CircleContactKind contact_kind = CircleContactKind::Empty;
    std::array<CircleContact, 2> contacts;
    AngularCoverage first_inside_second;
    AngularCoverage second_inside_first;

    constexpr int contact_count() const noexcept {
        if (contact_kind == CircleContactKind::Point) return 1;
        if (contact_kind == CircleContactKind::TwoPoints) return 2;
        return 0;
    }
};

struct CircleLinearContact {
    Point<long double> point;
    long double circle_argument = 0.0L;
    long double linear_parameter = 0.0L;
};

struct CircleLinearIntersection {
    int contact_count = 0;
    std::array<CircleLinearContact, 2> contacts;
};

namespace circle_detail {

inline int compare(long double first, long double second, long double eps) {
    if (first < second - eps) return -1;
    if (first > second + eps) return 1;
    return 0;
}

inline bool close(
    const Point<long double>& first,
    const Point<long double>& second,
    long double eps
) {
    return geometry::distance(first, second) <= eps;
}

inline void push_unique(
    std::vector<Point<long double>>& points,
    const Point<long double>& point,
    long double eps
) {
    for (const Point<long double>& existing : points) {
        if (close(existing, point, eps)) return;
    }
    points.push_back(point);
}

inline bool same_line(
    const Line<long double>& first,
    const Line<long double>& second,
    long double eps
) {
    Point<long double> first_direction = first.b - first.a;
    Point<long double> second_direction = second.b - second.a;
    if (std::fabs(cross(first_direction, second_direction)) > eps) {
        return false;
    }
    return std::fabs(cross(first_direction, second.a - first.a)) <= eps;
}

inline Line<long double> tangent_line(
    const Point<long double>& contact,
    Point<long double> normal,
    long double eps
) {
    Point<long double> direction(-normal.y, normal.x);
    if (
        direction.x < -eps ||
        (std::fabs(direction.x) <= eps && direction.y < 0)
    ) {
        direction = -direction;
    }
    return Line<long double>{contact, contact + direction};
}

inline long double circular_segment_angle_term(
    long double angle,
    long double sine,
    long double cosine
) {
    if (angle >= 0.01L) return angle - sine * cosine;
    const long double squared = angle * angle;
    return angle * squared * (
        2.0L / 3.0L +
        squared * (
            -2.0L / 15.0L +
            squared * (4.0L / 315.0L - squared * 2.0L / 2835.0L)
        )
    );
}

inline long double segment_disk_signed_area(
    const Point<long double>& first,
    const Point<long double>& second,
    long double radius,
    long double eps
) {
    const Point<long double> direction = second - first;
    const long double quadratic = dot(direction, direction);
    if (quadratic == 0.0L || radius == 0.0L) return 0.0L;

    std::vector<long double> cuts = {0.0L, 1.0L};
    const long double linear = 2.0L * dot(first, direction);
    const long double constant = dot(first, first) - radius * radius;
    const long double discriminant =
        linear * linear - 4.0L * quadratic * constant;
    const long double tolerance = eps * std::max({
        1.0L,
        std::fabs(linear * linear),
        std::fabs(4.0L * quadratic * constant)
    });
    if (discriminant >= -tolerance) {
        const long double root = std::sqrt(std::max(0.0L, discriminant));
        const long double first_ratio =
            (-linear - root) / (2.0L * quadratic);
        const long double second_ratio =
            (-linear + root) / (2.0L * quadratic);
        if (eps < first_ratio && first_ratio < 1.0L - eps) {
            cuts.push_back(first_ratio);
        }
        if (eps < second_ratio && second_ratio < 1.0L - eps) {
            cuts.push_back(second_ratio);
        }
    }
    std::sort(cuts.begin(), cuts.end());
    cuts.erase(
        std::unique(
            cuts.begin(),
            cuts.end(),
            [eps](long double left, long double right) {
                return std::fabs(left - right) <= eps;
            }
        ),
        cuts.end()
    );

    long double result = 0.0L;
    for (std::size_t index = 1; index < cuts.size(); ++index) {
        const long double left = cuts[index - 1];
        const long double right = cuts[index];
        const Point<long double> a = first + direction * left;
        const Point<long double> b = first + direction * right;
        const Point<long double> middle =
            first + direction * ((left + right) / 2.0L);
        if (norm(middle) <= radius + eps) {
            result += cross(a, b) / 2.0L;
        } else {
            result +=
                radius * radius * std::atan2(cross(a, b), dot(a, b)) /
                2.0L;
        }
    }
    return result;
}

}  // namespace circle_detail

template <Coordinate T>
constexpr Point<long double> centroid(const Circle<T>& circle) {
    assert(circle.radius >= 0);
    return Point<long double>(circle.center);
}

template <Coordinate T>
constexpr long double circle_circumference(const Circle<T>& circle) {
    assert(circle.radius >= 0);
    return
        2.0L * std::numbers::pi_v<long double> *
        static_cast<long double>(circle.radius);
}

template <Coordinate T>
constexpr long double circle_area(const Circle<T>& circle) {
    assert(circle.radius >= 0);
    const long double radius = static_cast<long double>(circle.radius);
    return std::numbers::pi_v<long double> * radius * radius;
}

inline long double normalize_circle_argument(long double argument) {
    const long double full = 2.0L * std::numbers::pi_v<long double>;
    argument = std::fmod(argument, full);
    if (argument < 0.0L) argument += full;
    if (argument == full) argument = 0.0L;
    return argument;
}

template <Coordinate T>
Point<long double> circle_point_at(
    const Circle<T>& circle,
    long double argument
) {
    assert(circle.radius >= 0);
    const long double radius = static_cast<long double>(circle.radius);
    return Point<long double>(circle.center) + Point<long double>(
        radius * std::cos(argument),
        radius * std::sin(argument)
    );
}

inline long double angular_measure(const AngularCoverage& coverage) {
    if (
        coverage.kind == AngularCoverageKind::Empty ||
        coverage.kind == AngularCoverageKind::Point
    ) {
        return 0.0L;
    }
    if (coverage.kind == AngularCoverageKind::Full) {
        return 2.0L * std::numbers::pi_v<long double>;
    }
    assert(coverage.kind == AngularCoverageKind::Arc);
    assert(coverage.begin <= coverage.end);
    return coverage.end - coverage.begin;
}

template <Coordinate T>
long double circle_arc_length(
    const Circle<T>& circle,
    const AngularCoverage& coverage
) {
    assert(circle.radius >= 0);
    return static_cast<long double>(circle.radius) * angular_measure(coverage);
}

template <Coordinate C, Coordinate P>
PointInCircle point_in_circle(
    const Circle<C>& circle,
    const Point<P>& point,
    long double eps = 1e-12L
) {
    assert(circle.radius >= 0);
    assert(eps >= 0.0L);
    if constexpr (ExactCoordinate<C> && ExactCoordinate<P>) {
        using W = std::common_type_t<wide_type<C>, wide_type<P>>;
        const W dx = W(point.x) - W(circle.center.x);
        const W dy = W(point.y) - W(circle.center.y);
        const W radius = W(circle.radius);
        const W squared_distance = dx * dx + dy * dy;
        const W squared_radius = radius * radius;
        if (squared_distance < squared_radius) return PointInCircle::Inside;
        if (squared_distance > squared_radius) return PointInCircle::Outside;
        return PointInCircle::Boundary;
    } else {
        const int relation = circle_detail::compare(
            geometry::distance(
                Point<long double>(circle.center),
                Point<long double>(point)
            ),
            static_cast<long double>(circle.radius),
            eps
        );
        if (relation < 0) return PointInCircle::Inside;
        if (relation > 0) return PointInCircle::Outside;
        return PointInCircle::Boundary;
    }
}

template <Coordinate C, Coordinate P>
bool contains(
    const Circle<C>& circle,
    const Point<P>& point,
    long double eps = 1e-12L
) {
    const PointInCircle relation = point_in_circle(circle, point, eps);
    return circle.filled
        ? relation != PointInCircle::Outside
        : relation == PointInCircle::Boundary;
}

template <Coordinate C, Coordinate P>
bool on_circle(
    const Circle<C>& circle,
    const Point<P>& point,
    long double eps = 1e-12L
) {
    assert(circle.radius >= 0);
    assert(eps >= 0.0L);
    if constexpr (ExactCoordinate<C> && ExactCoordinate<P>) {
        using W = std::common_type_t<wide_type<C>, wide_type<P>>;
        const W dx = W(point.x) - W(circle.center.x);
        const W dy = W(point.y) - W(circle.center.y);
        const W radius = W(circle.radius);
        return dx * dx + dy * dy == radius * radius;
    } else {
        return circle_detail::compare(
            geometry::distance(
                Point<long double>(circle.center),
                Point<long double>(point)
            ),
            static_cast<long double>(circle.radius),
            eps
        ) == 0;
    }
}

template <Coordinate C, Coordinate P>
long double circle_argument(
    const Circle<C>& circle,
    const Point<P>& point
) {
    assert(circle.radius >= 0);
    return normalize_circle_argument(std::atan2(
        static_cast<long double>(point.y) -
            static_cast<long double>(circle.center.y),
        static_cast<long double>(point.x) -
            static_cast<long double>(circle.center.x)
    ));
}

template <Coordinate C, Coordinate P>
bool intersects(
    const Circle<C>& circle,
    const Point<P>& point,
    long double eps = 1e-12L
) {
    return contains(circle, point, eps);
}

template <Coordinate P, Coordinate C>
bool intersects(
    const Point<P>& point,
    const Circle<C>& circle,
    long double eps = 1e-12L
) {
    return intersects(circle, point, eps);
}

template <Coordinate A, Coordinate B>
Circle<long double> circle_from_diameter(
    const Point<A>& first,
    const Point<B>& second
) {
    Point<long double> a(first);
    Point<long double> b(second);
    Point<long double> center = (a + b) / 2.0L;
    return Circle<long double>{center, geometry::distance(a, b) / 2.0L};
}

template <Coordinate T>
std::optional<Circle<long double>> incircle(
    const Point<T>& first,
    const Point<T>& second,
    const Point<T>& third,
    long double eps = 1e-12L
) {
    assert(eps >= 0.0L);
    if (orientation(first, second, third, eps) == 0) return std::nullopt;

    long double opposite_first = geometry::distance(second, third);
    long double opposite_second = geometry::distance(third, first);
    long double opposite_third = geometry::distance(first, second);
    long double perimeter =
        opposite_first + opposite_second + opposite_third;
    Point<long double> center =
        (Point<long double>(first) * opposite_first +
         Point<long double>(second) * opposite_second +
         Point<long double>(third) * opposite_third) /
        perimeter;
    long double doubled_area = std::fabs(
        static_cast<long double>(cross(first, second, third))
    );
    return Circle<long double>{center, doubled_area / perimeter};
}

template <Coordinate T>
std::optional<Circle<long double>> circumcircle(
    const Point<T>& first,
    const Point<T>& second,
    const Point<T>& third,
    long double eps = 1e-12L
) {
    assert(eps >= 0.0L);
    if (orientation(first, second, third, eps) == 0) return std::nullopt;

    Point<long double> origin(first);
    Point<long double> u = Point<long double>(second) - origin;
    Point<long double> v = Point<long double>(third) - origin;
    long double denominator = 2.0L * cross(u, v);
    long double u_norm = norm2(u);
    long double v_norm = norm2(v);
    Point<long double> offset(
        (u_norm * v.y - v_norm * u.y) / denominator,
        (u.x * v_norm - v.x * u_norm) / denominator
    );
    Point<long double> center = origin + offset;
    return Circle<long double>{center, norm(offset)};
}

template <Coordinate A, Coordinate B>
CircleRelation circle_relation(
    const Circle<A>& first,
    const Circle<B>& second,
    long double eps = 1e-12L
) {
    assert(first.radius >= 0);
    assert(second.radius >= 0);
    assert(eps >= 0.0L);
    if constexpr (ExactCoordinate<A> && ExactCoordinate<B>) {
        using W = std::common_type_t<wide_type<A>, wide_type<B>>;
        W dx = W(second.center.x) - W(first.center.x);
        W dy = W(second.center.y) - W(first.center.y);
        W squared_distance = dx * dx + dy * dy;
        W first_radius = W(first.radius);
        W second_radius = W(second.radius);
        W sum = first_radius + second_radius;
        W difference = first_radius - second_radius;
        if (difference < 0) difference = -difference;
        if (squared_distance == 0 && difference == 0) {
            return CircleRelation::Coincident;
        }
        if (squared_distance > sum * sum) return CircleRelation::Separate;
        if (squared_distance == sum * sum) {
            return CircleRelation::ExternallyTangent;
        }
        if (squared_distance < difference * difference) {
            return CircleRelation::Contained;
        }
        if (squared_distance == difference * difference) {
            return CircleRelation::InternallyTangent;
        }
        return CircleRelation::Intersecting;
    } else {
        long double center_distance = geometry::distance(
            Point<long double>(first.center),
            Point<long double>(second.center)
        );
        long double first_radius = static_cast<long double>(first.radius);
        long double second_radius = static_cast<long double>(second.radius);
        long double sum = first_radius + second_radius;
        long double difference = std::fabs(first_radius - second_radius);
        if (
            center_distance <= eps &&
            difference <= eps
        ) {
            return CircleRelation::Coincident;
        }
        int outer = circle_detail::compare(center_distance, sum, eps);
        if (outer > 0) return CircleRelation::Separate;
        if (outer == 0) return CircleRelation::ExternallyTangent;
        int inner = circle_detail::compare(center_distance, difference, eps);
        if (inner < 0) return CircleRelation::Contained;
        if (inner == 0) return CircleRelation::InternallyTangent;
        return CircleRelation::Intersecting;
    }
}

template <Coordinate C, Coordinate L>
CircleLinearIntersection circle_boundary_intersection(
    const Circle<C>& circle,
    const Line<L>& line,
    long double eps = 1e-12L
) {
    assert(circle.radius >= 0);
    assert(line.a != line.b);
    assert(eps >= 0.0L);

    const Point<long double> center(circle.center);
    const Point<long double> origin(line.a);
    const Point<long double> direction =
        Point<long double>(line.b) - origin;
    const long double squared_length = dot(direction, direction);
    const long double length = std::sqrt(squared_length);
    const long double foot_parameter =
        dot(center - origin, direction) / squared_length;
    const Point<long double> foot =
        origin + direction * foot_parameter;
    const long double distance_to_line = geometry::distance(center, foot);
    const long double radius = static_cast<long double>(circle.radius);
    const int relation =
        circle_detail::compare(distance_to_line, radius, eps);

    CircleLinearIntersection result;
    if (relation > 0) return result;
    if (relation == 0) {
        result.contact_count = 1;
        result.contacts[0] = CircleLinearContact{
            foot,
            circle_argument(circle, foot),
            foot_parameter
        };
        return result;
    }

    const long double offset = std::sqrt(std::max(
        0.0L,
        radius * radius - distance_to_line * distance_to_line
    ));
    const long double parameter_offset = offset / length;
    result.contact_count = 2;
    for (int index = 0; index < 2; ++index) {
        const long double parameter = foot_parameter +
            (index == 0 ? -parameter_offset : parameter_offset);
        const Point<long double> point = origin + direction * parameter;
        result.contacts[index] = CircleLinearContact{
            point,
            circle_argument(circle, point),
            parameter
        };
    }
    return result;
}

template <Coordinate L, Coordinate C>
CircleLinearIntersection circle_boundary_intersection(
    const Line<L>& line,
    const Circle<C>& circle,
    long double eps = 1e-12L
) {
    return circle_boundary_intersection(circle, line, eps);
}

template <Coordinate C, Coordinate R>
CircleLinearIntersection circle_boundary_intersection(
    const Circle<C>& circle,
    const Ray<R>& ray,
    long double eps = 1e-12L
) {
    assert(ray.origin != ray.through);
    const Line<R> line{ray.origin, ray.through};
    const CircleLinearIntersection line_result =
        circle_boundary_intersection(circle, line, eps);
    CircleLinearIntersection result;
    for (int index = 0; index < line_result.contact_count; ++index) {
        CircleLinearContact contact = line_result.contacts[index];
        if (contact.linear_parameter < -eps) continue;
        if (std::fabs(contact.linear_parameter) <= eps) {
            contact.linear_parameter = 0.0L;
            contact.point = Point<long double>(ray.origin);
            contact.circle_argument = circle_argument(circle, contact.point);
        }
        result.contacts[result.contact_count++] = contact;
    }
    return result;
}

template <Coordinate R, Coordinate C>
CircleLinearIntersection circle_boundary_intersection(
    const Ray<R>& ray,
    const Circle<C>& circle,
    long double eps = 1e-12L
) {
    return circle_boundary_intersection(circle, ray, eps);
}

template <Coordinate C, Coordinate S>
CircleLinearIntersection circle_boundary_intersection(
    const Circle<C>& circle,
    const Segment<S>& segment,
    long double eps = 1e-12L
) {
    assert(circle.radius >= 0);
    assert(eps >= 0.0L);
    CircleLinearIntersection result;
    if (segment.a == segment.b) {
        if (on_circle(circle, segment.a, eps)) {
            const Point<long double> point(segment.a);
            result.contact_count = 1;
            result.contacts[0] = CircleLinearContact{
                point,
                circle_argument(circle, point),
                0.0L
            };
        }
        return result;
    }

    const Line<S> line{segment.a, segment.b};
    const CircleLinearIntersection line_result =
        circle_boundary_intersection(circle, line, eps);
    for (int index = 0; index < line_result.contact_count; ++index) {
        CircleLinearContact contact = line_result.contacts[index];
        if (
            contact.linear_parameter < -eps ||
            contact.linear_parameter > 1.0L + eps
        ) {
            continue;
        }
        if (std::fabs(contact.linear_parameter) <= eps) {
            contact.linear_parameter = 0.0L;
            contact.point = Point<long double>(segment.a);
        } else if (std::fabs(contact.linear_parameter - 1.0L) <= eps) {
            contact.linear_parameter = 1.0L;
            contact.point = Point<long double>(segment.b);
        }
        contact.circle_argument = circle_argument(circle, contact.point);
        result.contacts[result.contact_count++] = contact;
    }
    return result;
}

template <Coordinate S, Coordinate C>
CircleLinearIntersection circle_boundary_intersection(
    const Segment<S>& segment,
    const Circle<C>& circle,
    long double eps = 1e-12L
) {
    return circle_boundary_intersection(circle, segment, eps);
}

template <Coordinate A, Coordinate B>
CircleCircleIntersection circle_boundary_intersection(
    const Circle<A>& first,
    const Circle<B>& second,
    long double eps = 1e-12L
) {
    assert(first.radius >= 0);
    assert(second.radius >= 0);
    assert(eps >= 0.0L);
    const long double full = 2.0L * std::numbers::pi_v<long double>;
    const long double first_radius = static_cast<long double>(first.radius);
    const long double second_radius = static_cast<long double>(second.radius);
    CircleCircleIntersection result;
    result.relation = circle_relation(first, second, eps);

    auto point_coverage = [](long double argument) {
        return AngularCoverage{
            AngularCoverageKind::Point,
            argument,
            argument
        };
    };
    auto full_coverage = [full]() {
        return AngularCoverage{AngularCoverageKind::Full, 0.0L, full};
    };

    if (result.relation == CircleRelation::Coincident) {
        if (first_radius == 0.0L) {
            const Point<long double> point(first.center);
            result.contact_kind = CircleContactKind::Point;
            result.contacts[0] = CircleContact{point, 0.0L, 0.0L};
            result.first_inside_second = point_coverage(0.0L);
            result.second_inside_first = point_coverage(0.0L);
        } else {
            result.contact_kind = CircleContactKind::Coincident;
            result.first_inside_second = full_coverage();
            result.second_inside_first = full_coverage();
        }
        return result;
    }

    if (result.relation == CircleRelation::Separate) return result;
    if (result.relation == CircleRelation::Contained) {
        if (first_radius < second_radius) {
            result.first_inside_second = first_radius == 0.0L
                ? point_coverage(0.0L)
                : full_coverage();
        } else {
            result.second_inside_first = second_radius == 0.0L
                ? point_coverage(0.0L)
                : full_coverage();
        }
        return result;
    }

    const Point<long double> first_center(first.center);
    const Point<long double> second_center(second.center);
    const Point<long double> center_direction = second_center - first_center;
    const long double center_distance = norm(center_direction);
    const Point<long double> unit = center_direction / center_distance;
    const long double along =
        (first_radius * first_radius - second_radius * second_radius +
         center_distance * center_distance) /
        (2.0L * center_distance);
    const Point<long double> base = first_center + unit * along;

    if (
        result.relation == CircleRelation::ExternallyTangent ||
        result.relation == CircleRelation::InternallyTangent
    ) {
        const long double first_argument =
            circle_argument(first, base);
        const long double second_argument =
            circle_argument(second, base);
        result.contact_kind = CircleContactKind::Point;
        result.contacts[0] = CircleContact{
            base,
            first_argument,
            second_argument
        };
        result.first_inside_second = point_coverage(first_argument);
        result.second_inside_first = point_coverage(second_argument);
        if (result.relation == CircleRelation::InternallyTangent) {
            if (first_radius < second_radius && first_radius > 0.0L) {
                result.first_inside_second = full_coverage();
            } else if (
                second_radius < first_radius && second_radius > 0.0L
            ) {
                result.second_inside_first = full_coverage();
            }
        }
        return result;
    }

    assert(result.relation == CircleRelation::Intersecting);
    const long double height = std::sqrt(std::max(
        0.0L,
        first_radius * first_radius - along * along
    ));
    const Point<long double> perpendicular(-unit.y, unit.x);
    const Point<long double> first_point = base - perpendicular * height;
    const Point<long double> second_point = base + perpendicular * height;
    result.contact_kind = CircleContactKind::TwoPoints;
    result.contacts[0] = CircleContact{
        first_point,
        circle_argument(first, first_point),
        circle_argument(second, first_point)
    };
    result.contacts[1] = CircleContact{
        second_point,
        circle_argument(first, second_point),
        circle_argument(second, second_point)
    };

    const long double first_begin = result.contacts[0].first_argument;
    long double first_end = result.contacts[1].first_argument;
    if (first_end <= first_begin) first_end += full;
    result.first_inside_second = AngularCoverage{
        AngularCoverageKind::Arc,
        first_begin,
        first_end
    };

    const long double second_begin = result.contacts[1].second_argument;
    long double second_end = result.contacts[0].second_argument;
    if (second_end <= second_begin) second_end += full;
    result.second_inside_first = AngularCoverage{
        AngularCoverageKind::Arc,
        second_begin,
        second_end
    };
    return result;
}

template <Coordinate C, Coordinate L>
bool intersects(
    const Circle<C>& circle,
    const Line<L>& line,
    long double eps = 1e-12L
) {
    if (circle.filled) {
        const Line<long double> converted{
            Point<long double>(line.a),
            Point<long double>(line.b)
        };
        return contains(
            circle,
            projection(converted, Point<long double>(circle.center)),
            eps
        );
    }
    return circle_boundary_intersection(circle, line, eps).contact_count > 0;
}

template <Coordinate C, Coordinate L>
bool intersects(
    const Line<L>& line,
    const Circle<C>& circle,
    long double eps = 1e-12L
) {
    return intersects(circle, line, eps);
}

template <Coordinate C, Coordinate R>
bool intersects(
    const Circle<C>& circle,
    const Ray<R>& ray,
    long double eps = 1e-12L
) {
    if (circle.filled) {
        const Ray<long double> converted{
            Point<long double>(ray.origin),
            Point<long double>(ray.through)
        };
        return contains(
            circle,
            projection(converted, Point<long double>(circle.center)),
            eps
        );
    }
    return circle_boundary_intersection(circle, ray, eps).contact_count > 0;
}

template <Coordinate C, Coordinate R>
bool intersects(
    const Ray<R>& ray,
    const Circle<C>& circle,
    long double eps = 1e-12L
) {
    return intersects(circle, ray, eps);
}

template <Coordinate C, Coordinate S>
bool intersects(
    const Circle<C>& circle,
    const Segment<S>& segment,
    long double eps = 1e-12L
) {
    if (circle.filled) {
        const Segment<long double> converted{
            Point<long double>(segment.a),
            Point<long double>(segment.b)
        };
        return contains(
            circle,
            projection(converted, Point<long double>(circle.center)),
            eps
        );
    }
    return
        circle_boundary_intersection(circle, segment, eps).contact_count > 0;
}

template <Coordinate C, Coordinate S>
bool intersects(
    const Segment<S>& segment,
    const Circle<C>& circle,
    long double eps = 1e-12L
) {
    return intersects(circle, segment, eps);
}

template <Coordinate A, Coordinate B>
bool intersects(
    const Circle<A>& first,
    const Circle<B>& second,
    long double eps = 1e-12L
) {
    assert(first.radius >= 0);
    assert(second.radius >= 0);
    assert(eps >= 0.0L);
    if (first.filled && second.filled) {
        if constexpr (ExactCoordinate<A> && ExactCoordinate<B>) {
            using W = std::common_type_t<wide_type<A>, wide_type<B>>;
            const W dx = W(second.center.x) - W(first.center.x);
            const W dy = W(second.center.y) - W(first.center.y);
            const W radius = W(first.radius) + W(second.radius);
            return dx * dx + dy * dy <= radius * radius;
        } else {
            const long double center_distance = geometry::distance(
                Point<long double>(first.center),
                Point<long double>(second.center)
            );
            const long double radius_sum =
                static_cast<long double>(first.radius) +
                static_cast<long double>(second.radius);
            return circle_detail::compare(
                center_distance,
                radius_sum,
                eps
            ) <= 0;
        }
    }
    if (first.filled != second.filled) {
        const long double center_distance = geometry::distance(
            Point<long double>(first.center),
            Point<long double>(second.center)
        );
        const long double boundary_radius = first.filled
            ? static_cast<long double>(second.radius)
            : static_cast<long double>(first.radius);
        const long double filled_radius = first.filled
            ? static_cast<long double>(first.radius)
            : static_cast<long double>(second.radius);
        return circle_detail::compare(
            std::fabs(center_distance - boundary_radius),
            filled_radius,
            eps
        ) <= 0;
    }
    CircleRelation relation = circle_relation(first, second, eps);
    return
        relation == CircleRelation::ExternallyTangent ||
        relation == CircleRelation::Intersecting ||
        relation == CircleRelation::InternallyTangent ||
        relation == CircleRelation::Coincident;
}

template <Coordinate R, Coordinate H, Coordinate C>
Ray<long double> reflected_ray(
    const Ray<R>& incoming,
    const Point<H>& hit,
    const Circle<C>& circle,
    long double eps = 1e-12L
) {
    assert(incoming.origin != incoming.through);
    assert(eps >= 0.0L);
    assert(static_cast<long double>(circle.radius) > eps);
    assert(
        std::fabs(
            geometry::distance(
                Point<long double>(hit),
                Point<long double>(circle.center)
            ) -
            static_cast<long double>(circle.radius)
        ) <= eps
    );

    Point<long double> hit_point(hit);
    Point<long double> normal = normalized(
        hit_point - Point<long double>(circle.center)
    );
    Point<long double> incoming_direction =
        Point<long double>(incoming.through) -
        Point<long double>(incoming.origin);
    Point<long double> outgoing_direction =
        incoming_direction - normal * (2.0L * dot(incoming_direction, normal));
    return Ray<long double>{hit_point, hit_point + outgoing_direction};
}

template <Coordinate C, Coordinate P>
std::vector<Point<long double>> tangent_points(
    const Circle<C>& circle,
    const Point<P>& point,
    long double eps = 1e-12L
) {
    assert(circle.radius >= 0);
    assert(eps >= 0.0L);
    Point<long double> center(circle.center);
    Point<long double> external(point);
    Point<long double> direction = external - center;
    long double squared_distance = dot(direction, direction);
    long double radius = static_cast<long double>(circle.radius);
    if (radius == 0.0L) return {center};

    long double center_distance = std::sqrt(squared_distance);
    int relation = circle_detail::compare(center_distance, radius, eps);
    if (relation < 0) return {};
    if (relation == 0) {
        return {center + direction * (radius / center_distance)};
    }

    Point<long double> base =
        center + direction * (radius * radius / squared_distance);
    long double scale =
        radius * std::sqrt(std::max(
            0.0L,
            squared_distance - radius * radius
        )) /
        squared_distance;
    Point<long double> perpendicular(-direction.y, direction.x);
    Point<long double> first = base - perpendicular * scale;
    Point<long double> second = base + perpendicular * scale;
    if (second < first) std::swap(first, second);
    return {first, second};
}

template <Coordinate A, Coordinate B>
std::vector<Line<long double>> common_tangents(
    const Circle<A>& first,
    const Circle<B>& second,
    long double eps = 1e-12L
) {
    assert(first.radius >= 0);
    assert(second.radius >= 0);
    assert(eps >= 0.0L);
    Point<long double> first_center(first.center);
    Point<long double> second_center(second.center);
    Point<long double> direction = second_center - first_center;
    long double squared_distance = dot(direction, direction);
    long double center_distance = std::sqrt(squared_distance);
    if (center_distance <= eps) return {};

    long double first_radius = static_cast<long double>(first.radius);
    long double second_radius = static_cast<long double>(second.radius);
    std::vector<Line<long double>> result;
    for (int second_side : {1, -1}) {
        long double difference =
            first_radius - second_side * second_radius;
        int relation = circle_detail::compare(
            std::fabs(difference),
            center_distance,
            eps
        );
        if (relation > 0) continue;
        long double perpendicular_length = relation == 0 ? 0.0L : std::sqrt(
            std::max(0.0L, squared_distance - difference * difference)
        );
        int choices = perpendicular_length <= eps ? 1 : 2;
        for (int choice = 0; choice < choices; ++choice) {
            long double side = choice == 0 ? -1.0L : 1.0L;
            Point<long double> normal =
                direction * (difference / squared_distance) +
                Point<long double>(-direction.y, direction.x) *
                    (side * perpendicular_length / squared_distance);
            normal = normalized(normal);
            Point<long double> contact =
                first_center + normal * first_radius;
            Line<long double> tangent =
                circle_detail::tangent_line(contact, normal, eps);
            bool duplicate = false;
            for (const Line<long double>& existing : result) {
                if (circle_detail::same_line(existing, tangent, eps)) {
                    duplicate = true;
                    break;
                }
            }
            if (!duplicate) result.push_back(tangent);
        }
    }
    std::sort(
        result.begin(),
        result.end(),
        [](const Line<long double>& left, const Line<long double>& right) {
            if (left.a != right.a) return left.a < right.a;
            return left.b < right.b;
        }
    );
    return result;
}

template <Coordinate A, Coordinate B>
std::vector<Point<long double>> common_tangent_points(
    const Circle<A>& first,
    const Circle<B>& second,
    long double eps = 1e-12L
) {
    std::vector<Point<long double>> result;
    for (const Line<long double>& line : common_tangents(first, second, eps)) {
        circle_detail::push_unique(result, line.a, eps);
    }
    std::sort(result.begin(), result.end());
    return result;
}

// These area functions use the enclosed disks, independent of `filled`.
template <Coordinate A, Coordinate B>
long double circle_circle_intersection_area(
    const Circle<A>& first,
    const Circle<B>& second,
    long double eps = 1e-12L
) {
    assert(first.radius >= 0);
    assert(second.radius >= 0);
    assert(eps >= 0.0L);
    const long double first_radius = static_cast<long double>(first.radius);
    const long double second_radius = static_cast<long double>(second.radius);
    const CircleRelation relation = circle_relation(first, second, eps);
    if (
        relation == CircleRelation::Separate ||
        relation == CircleRelation::ExternallyTangent
    ) {
        return 0.0L;
    }
    if (
        relation == CircleRelation::Contained ||
        relation == CircleRelation::InternallyTangent ||
        relation == CircleRelation::Coincident
    ) {
        const long double radius = std::min(first_radius, second_radius);
        return std::numbers::pi_v<long double> * radius * radius;
    }

    const long double center_distance = geometry::distance(
        Point<long double>(first.center),
        Point<long double>(second.center)
    );
    const long double first_cosine = std::clamp(
        (
            (center_distance - second_radius) *
                (center_distance + second_radius) +
            first_radius * first_radius
        ) / (2.0L * center_distance * first_radius),
        -1.0L,
        1.0L
    );
    const long double second_cosine = std::clamp(
        (
            (center_distance - first_radius) *
                (center_distance + first_radius) +
            second_radius * second_radius
        ) / (2.0L * center_distance * second_radius),
        -1.0L,
        1.0L
    );
    const long double radicand =
        (-center_distance + first_radius + second_radius) *
        (center_distance + first_radius - second_radius) *
        (center_distance - first_radius + second_radius) *
        (center_distance + first_radius + second_radius);
    const long double height =
        std::sqrt(std::max(0.0L, radicand)) / (2.0L * center_distance);
    const long double first_sine =
        std::clamp(height / first_radius, 0.0L, 1.0L);
    const long double second_sine =
        std::clamp(height / second_radius, 0.0L, 1.0L);
    const long double first_angle = std::atan2(first_sine, first_cosine);
    const long double second_angle = std::atan2(second_sine, second_cosine);
    return
        first_radius * first_radius *
            circle_detail::circular_segment_angle_term(
                first_angle,
                first_sine,
                first_cosine
            ) +
        second_radius * second_radius *
            circle_detail::circular_segment_angle_term(
                second_angle,
                second_sine,
                second_cosine
            );
}

template <Coordinate C, Coordinate P>
long double circle_polygon_intersection_area(
    const Circle<C>& circle,
    const std::vector<Point<P>>& polygon,
    long double eps = 1e-12L
) {
    assert(circle.radius >= 0);
    assert(eps >= 0.0L);
    if (polygon.empty() || circle.radius == 0) return 0.0L;

    const Point<long double> center(circle.center);
    const long double radius = static_cast<long double>(circle.radius);
    long double result = 0.0L;
    for (std::size_t index = 0; index < polygon.size(); ++index) {
        const Point<long double> first =
            Point<long double>(polygon[index]) - center;
        const Point<long double> second =
            Point<long double>(polygon[(index + 1) % polygon.size()]) - center;
        result += circle_detail::segment_disk_signed_area(
            first,
            second,
            radius,
            eps
        );
    }
    return std::fabs(result);
}

namespace circle_detail {

template <Coordinate T>
Point<long double> point_toward(
    const Circle<T>& circle,
    const Point<long double>& target
) {
    assert(circle.radius >= 0);
    const Point<long double> center(circle.center);
    const long double radius = static_cast<long double>(circle.radius);
    const Point<long double> direction = target - center;
    const long double length = norm(direction);
    if (length == 0.0L) {
        return center + Point<long double>(-radius, 0.0L);
    }
    return center + direction * (radius / length);
}

inline void consider(
    ClosestPoints& best,
    const ClosestPoints& candidate
) {
    closest_points_detail::consider(best, candidate);
}

}  // namespace circle_detail

template <Coordinate C, Coordinate P>
ClosestPoints closest_points(
    const Circle<C>& circle,
    const Point<P>& point,
    long double eps = 1e-12L
) {
    const Point<long double> converted(point);
    if (circle.filled && contains(circle, converted, eps)) {
        return ClosestPoints{converted, converted};
    }
    return ClosestPoints{
        circle_detail::point_toward(circle, converted),
        converted
    };
}

template <Coordinate P, Coordinate C>
ClosestPoints closest_points(
    const Point<P>& point,
    const Circle<C>& circle,
    long double eps = 1e-12L
) {
    return closest_points_detail::reversed(
        closest_points(circle, point, eps)
    );
}

template <Coordinate C, Coordinate L>
ClosestPoints closest_points(
    const Circle<C>& circle,
    const Line<L>& line,
    long double eps = 1e-12L
) {
    const Line<long double> converted{
        Point<long double>(line.a),
        Point<long double>(line.b)
    };
    const Point<long double> point = projection(
        converted,
        Point<long double>(circle.center)
    );
    if (circle.filled) return closest_points(circle, point, eps);

    const CircleLinearIntersection common =
        circle_boundary_intersection(circle, line, eps);
    if (common.contact_count > 0) {
        return ClosestPoints{
            common.contacts[0].point,
            common.contacts[0].point
        };
    }
    return ClosestPoints{
        circle_detail::point_toward(circle, point),
        point
    };
}

template <Coordinate L, Coordinate C>
ClosestPoints closest_points(
    const Line<L>& line,
    const Circle<C>& circle,
    long double eps = 1e-12L
) {
    return closest_points_detail::reversed(closest_points(circle, line, eps));
}

template <Coordinate C, Coordinate R>
ClosestPoints closest_points(
    const Circle<C>& circle,
    const Ray<R>& ray,
    long double eps = 1e-12L
) {
    const Ray<long double> converted{
        Point<long double>(ray.origin),
        Point<long double>(ray.through)
    };
    const Point<long double> point = projection(
        converted,
        Point<long double>(circle.center)
    );
    if (circle.filled) return closest_points(circle, point, eps);

    const CircleLinearIntersection common =
        circle_boundary_intersection(circle, ray, eps);
    if (common.contact_count > 0) {
        return ClosestPoints{
            common.contacts[0].point,
            common.contacts[0].point
        };
    }
    return ClosestPoints{
        circle_detail::point_toward(circle, point),
        point
    };
}

template <Coordinate R, Coordinate C>
ClosestPoints closest_points(
    const Ray<R>& ray,
    const Circle<C>& circle,
    long double eps = 1e-12L
) {
    return closest_points_detail::reversed(closest_points(circle, ray, eps));
}

template <Coordinate C, Coordinate S>
ClosestPoints closest_points(
    const Circle<C>& circle,
    const Segment<S>& segment,
    long double eps = 1e-12L
) {
    const Segment<long double> converted{
        Point<long double>(segment.a),
        Point<long double>(segment.b)
    };
    const Point<long double> center(circle.center);
    const Point<long double> projected = projection(converted, center);
    if (circle.filled) return closest_points(circle, projected, eps);

    const CircleLinearIntersection common =
        circle_boundary_intersection(circle, segment, eps);
    if (common.contact_count > 0) {
        return ClosestPoints{
            common.contacts[0].point,
            common.contacts[0].point
        };
    }
    ClosestPoints result{
        circle_detail::point_toward(circle, projected),
        projected
    };
    for (const Point<long double>& point : {converted.a, converted.b}) {
        circle_detail::consider(
            result,
            ClosestPoints{circle_detail::point_toward(circle, point), point}
        );
    }
    return result;
}

template <Coordinate S, Coordinate C>
ClosestPoints closest_points(
    const Segment<S>& segment,
    const Circle<C>& circle,
    long double eps = 1e-12L
) {
    return closest_points_detail::reversed(
        closest_points(circle, segment, eps)
    );
}

template <Coordinate A, Coordinate B>
ClosestPoints closest_points(
    const Circle<A>& first,
    const Circle<B>& second,
    long double eps = 1e-12L
) {
    if (first.filled && !second.filled) {
        return closest_points_detail::reversed(
            closest_points(second, first, eps)
        );
    }

    if (!first.filled && second.filled) {
        const ClosestPoints center_result =
            closest_points(first, second.center, eps);
        if (contains(second, center_result.first, eps)) {
            return ClosestPoints{center_result.first, center_result.first};
        }
        const ClosestPoints filled_result =
            closest_points(second, center_result.first, eps);
        return ClosestPoints{center_result.first, filled_result.first};
    }

    if (first.filled && second.filled) {
        assert(first.radius >= 0);
        assert(second.radius >= 0);
        const Point<long double> first_center(first.center);
        const Point<long double> second_center(second.center);
        Point<long double> direction = second_center - first_center;
        const long double center_distance = norm(direction);
        if (center_distance == 0.0L) {
            return ClosestPoints{first_center, first_center};
        }
        direction = direction / center_distance;
        const long double first_radius =
            static_cast<long double>(first.radius);
        const long double second_radius =
            static_cast<long double>(second.radius);
        if (intersects(first, second, eps)) {
            const long double left = std::max(
                -first_radius,
                center_distance - second_radius
            );
            const long double right = std::min(
                first_radius,
                center_distance + second_radius
            );
            const Point<long double> common =
                first_center + direction * ((left + right) / 2.0L);
            return ClosestPoints{common, common};
        }
        return ClosestPoints{
            first_center + direction * first_radius,
            second_center - direction * second_radius
        };
    }

    const CircleCircleIntersection common =
        circle_boundary_intersection(first, second, eps);
    if (common.contact_count() > 0) {
        return ClosestPoints{
            common.contacts[0].point,
            common.contacts[0].point
        };
    }

    const Point<long double> first_center(first.center);
    const Point<long double> second_center(second.center);
    if (circle_relation(first, second, eps) == CircleRelation::Coincident) {
        const Point<long double> point =
            circle_detail::point_toward(first, first_center);
        return ClosestPoints{point, point};
    }
    Point<long double> direction = second_center - first_center;
    const long double center_distance = norm(direction);
    if (center_distance == 0.0L) {
        const Point<long double> first_point =
            circle_detail::point_toward(first, first_center);
        const Point<long double> second_point =
            circle_detail::point_toward(second, second_center);
        return ClosestPoints{first_point, second_point};
    }
    direction = direction / center_distance;
    const long double first_radius = static_cast<long double>(first.radius);
    const long double second_radius = static_cast<long double>(second.radius);
    ClosestPoints result{
        first_center + direction * first_radius,
        second_center + direction * second_radius
    };
    for (const long double first_sign : {-1.0L, 1.0L}) {
        for (const long double second_sign : {-1.0L, 1.0L}) {
            circle_detail::consider(
                result,
                ClosestPoints{
                    first_center + direction * (first_sign * first_radius),
                    second_center + direction * (second_sign * second_radius)
                }
            );
        }
    }
    return result;
}

template <Coordinate C, Coordinate P>
long double distance(const Circle<C>& circle, const Point<P>& point) {
    const ClosestPoints result = closest_points(circle, point);
    return geometry::distance(result.first, result.second);
}

template <Coordinate P, Coordinate C>
long double distance(const Point<P>& point, const Circle<C>& circle) {
    return distance(circle, point);
}

template <Coordinate C, Coordinate L>
long double distance(const Circle<C>& circle, const Line<L>& line) {
    const ClosestPoints result = closest_points(circle, line);
    return geometry::distance(result.first, result.second);
}

template <Coordinate L, Coordinate C>
long double distance(const Line<L>& line, const Circle<C>& circle) {
    return distance(circle, line);
}

template <Coordinate C, Coordinate R>
long double distance(const Circle<C>& circle, const Ray<R>& ray) {
    const ClosestPoints result = closest_points(circle, ray);
    return geometry::distance(result.first, result.second);
}

template <Coordinate R, Coordinate C>
long double distance(const Ray<R>& ray, const Circle<C>& circle) {
    return distance(circle, ray);
}

template <Coordinate C, Coordinate S>
long double distance(const Circle<C>& circle, const Segment<S>& segment) {
    const ClosestPoints result = closest_points(circle, segment);
    return geometry::distance(result.first, result.second);
}

template <Coordinate S, Coordinate C>
long double distance(const Segment<S>& segment, const Circle<C>& circle) {
    return distance(circle, segment);
}

template <Coordinate A, Coordinate B>
long double distance(const Circle<A>& first, const Circle<B>& second) {
    const ClosestPoints result = closest_points(first, second);
    return geometry::distance(result.first, result.second);
}

}  // namespace geometry
}  // namespace m1une


#line 4 "verify/geometry/circle_relation.test.cpp"

#line 1 "utilities/fast_io.hpp"



#line 6 "utilities/fast_io.hpp"
#include <cerrno>
#include <charconv>
#line 9 "utilities/fast_io.hpp"
#include <cstdio>
#include <cstdlib>
#include <cstdint>
#include <cstring>
#include <iterator>
#include <string>
#include <sys/stat.h>
#line 17 "utilities/fast_io.hpp"
#include <utility>
#include <unistd.h>
#line 20 "utilities/fast_io.hpp"

namespace m1une {
namespace utilities {

struct FastOutput;

namespace internal {

// Shared with the convenience helpers in template.hpp.
inline FastOutput* standard_output_instance = nullptr;

// Detect std::begin(x), std::end(x).
template <class T, class = void>
struct is_range : std::false_type {};

template <class T>
struct is_range<T, std::void_t<
    decltype(std::begin(std::declval<T&>())),
    decltype(std::end(std::declval<T&>()))
>> : std::true_type {};

template <class T>
inline constexpr bool is_range_v = is_range<T>::value;

template <class T>
using range_reference_t = decltype(*std::begin(std::declval<T&>()));

template <class T>
using range_value_t = std::remove_cv_t<std::remove_reference_t<range_reference_t<T>>>;

template <class T, class = void>
struct range_stored_value {
    using type = range_value_t<T>;
};

template <class T>
struct range_stored_value<T, std::void_t<typename std::remove_cv_t<std::remove_reference_t<T>>::value_type>> {
    using type = typename std::remove_cv_t<std::remove_reference_t<T>>::value_type;
};

template <class T>
using range_stored_value_t = typename range_stored_value<T>::type;

// Treat strings and C strings as scalar output objects, not as ranges.
template <class T>
struct is_char_array : std::false_type {};

template <class T, std::size_t N>
struct is_char_array<T[N]>
    : std::bool_constant<std::is_same_v<std::remove_cv_t<T>, char>> {};

template <class T>
struct is_string_like
    : std::bool_constant<
          std::is_same_v<std::decay_t<T>, std::string>
          || std::is_same_v<std::decay_t<T>, const char*>
          || std::is_same_v<std::decay_t<T>, char*>
          || is_char_array<std::remove_reference_t<T>>::value
      > {};

template <class T>
inline constexpr bool is_string_like_v = is_string_like<T>::value;

// ModInt-like type: x.val() is printable, and x can be assigned from long long.
template <class T, class = void>
struct has_val_method : std::false_type {};

template <class T>
struct has_val_method<T, std::void_t<decltype(std::declval<const T&>().val())>>
    : std::true_type {};

template <class T>
inline constexpr bool has_val_method_v = has_val_method<T>::value;

template <class T, class = void>
struct has_static_mod_raw : std::false_type {};

template <class T>
struct has_static_mod_raw<
    T, std::void_t<decltype(T::mod()), decltype(T::raw(std::declval<uint32_t>()))>>
    : std::true_type {};

template <class T>
inline constexpr bool has_static_mod_raw_v = has_static_mod_raw<T>::value;

// libstdc++ before GCC 16 does not classify __int128 as an integral type in
// strict ISO modes such as -std=c++23. Keep the fast-I/O interface independent
// of that implementation detail.
template <class T>
inline constexpr bool is_integral_v =
    std::is_integral_v<T>
    || std::is_same_v<std::remove_cv_t<T>, __int128_t>
    || std::is_same_v<std::remove_cv_t<T>, __uint128_t>;

template <class T>
inline constexpr bool is_signed_v =
    std::is_signed_v<T>
    || std::is_same_v<std::remove_cv_t<T>, __int128_t>;

template <class T>
struct make_unsigned {
    using type = std::make_unsigned_t<T>;
};

template <>
struct make_unsigned<__int128_t> {
    using type = __uint128_t;
};

template <>
struct make_unsigned<__uint128_t> {
    using type = __uint128_t;
};

template <class T>
using make_unsigned_t = typename make_unsigned<std::remove_cv_t<T>>::type;

}  // namespace internal

struct FastInput {
    static constexpr int buffer_size = 1 << 20;

   private:
    std::FILE* _stream;
    char _buffer[buffer_size];
    int _position;
    int _length;
    int _file_descriptor;
    bool _streaming;

    bool refill() {
        _position = 0;
        if (_streaming) {
            ssize_t length;
            do {
                length = ::read(_file_descriptor, _buffer, buffer_size);
            } while (length < 0 && errno == EINTR);
            if (length <= 0) {
                _length = 0;
                return false;
            }
            _length = int(length);
        } else {
            _length = int(std::fread(_buffer, 1, buffer_size, _stream));
        }
        return _length != 0;
    }

    template <class T>
    bool read_integer_from_stream(T& value) {
        if (!skip_spaces()) return false;
        int c = read_char_raw();

        bool negative = false;
        if (c == '-') {
            negative = true;
            c = read_char_raw();
        }

        if constexpr (internal::is_signed_v<T>) {
            T result = 0;
            while ('0' <= c && c <= '9') {
                result = negative ? result * 10 - (c - '0')
                                  : result * 10 + (c - '0');
                c = read_char_raw();
            }
            value = result;
        } else {
            T result = 0;
            while ('0' <= c && c <= '9') {
                result = result * 10 + T(c - '0');
                c = read_char_raw();
            }
            value = negative ? T(0) - result : result;
        }
        return true;
    }

    bool prepare_number() {
        if (_length - _position >= 64) return true;
        const int remaining = _length - _position;
        if (remaining > 0) std::memmove(_buffer, _buffer + _position, remaining);
        const int added = int(std::fread(_buffer + remaining, 1, buffer_size - remaining, _stream));
        _position = 0;
        _length = remaining + added;
        if (_length < buffer_size) _buffer[_length] = '\0';
        return _length != 0;
    }

   public:
    explicit FastInput(std::FILE* stream = stdin)
        : _stream(stream),
          _position(0),
          _length(0),
          _file_descriptor(::fileno(stream)),
          _streaming([&] {
              struct stat status;
              return _file_descriptor >= 0
                     && ::fstat(_file_descriptor, &status) == 0
                     && !S_ISREG(status.st_mode);
          }()) {}

    FastInput(const FastInput&) = delete;
    FastInput& operator=(const FastInput&) = delete;

    int read_char_raw() {
        if (_position == _length && !refill()) return EOF;
        return _buffer[_position++];
    }

    bool skip_spaces() {
        int c = read_char_raw();
        while (c != EOF && c <= ' ') c = read_char_raw();
        if (c == EOF) return false;
        --_position;
        return true;
    }

    bool read(char& value) {
        if (!skip_spaces()) return false;
        value = char(read_char_raw());
        return true;
    }

    bool read(std::string& value) {
        if (!skip_spaces()) return false;
        value.clear();
        while (true) {
            const int begin = _position;
            while (_position < _length &&
                   static_cast<unsigned char>(_buffer[_position]) > ' ') {
                ++_position;
            }
            value.append(_buffer + begin, _position - begin);
            if (_position < _length) {
                ++_position;
                return true;
            }
            if (!refill()) return true;
        }
    }

    bool read(bool& value) {
        int x;
        if (!read(x)) return false;
        value = x != 0;
        return true;
    }

    template <class T>
    std::enable_if_t<
        internal::is_integral_v<T>
            && !std::is_same_v<std::remove_cv_t<T>, bool>
            && !std::is_same_v<std::remove_cv_t<T>, char>,
        bool
    >
    read(T& value) {
        if (_streaming) return read_integer_from_stream(value);
        if (!prepare_number()) return false;
        int c = static_cast<unsigned char>(_buffer[_position++]);
        while (c <= ' ') c = static_cast<unsigned char>(_buffer[_position++]);

        bool negative = false;
        if (c == '-') {
            negative = true;
            c = static_cast<unsigned char>(_buffer[_position++]);
        }

        if constexpr (internal::is_signed_v<T>) {
            T result = 0;
            while ('0' <= c && c <= '9') {
                const int first = c - '0';
                const int second = static_cast<unsigned char>(_buffer[_position]) - '0';
                if (0 <= second && second <= 9) {
                    result = negative ? result * 100 - (first * 10 + second)
                                      : result * 100 + (first * 10 + second);
                    ++_position;
                } else {
                    result = negative ? result * 10 - first : result * 10 + first;
                }
                c = static_cast<unsigned char>(_buffer[_position++]);
            }
            value = result;
        } else {
            T result = 0;
            while ('0' <= c && c <= '9') {
                const unsigned first = unsigned(c - '0');
                const int second = static_cast<unsigned char>(_buffer[_position]) - '0';
                if (0 <= second && second <= 9) {
                    result = result * 100 + T(first * 10 + unsigned(second));
                    ++_position;
                } else {
                    result = result * 10 + T(first);
                }
                c = static_cast<unsigned char>(_buffer[_position++]);
            }
            value = negative ? T(0) - result : result;
        }
        if (_position > _length) _position = _length;
        return true;
    }

    template <class T>
    std::enable_if_t<std::is_floating_point_v<T>, bool>
    read(T& value) {
        if (!skip_spaces()) return false;
        int c = read_char_raw();
        bool negative = false;
        if (c == '-' || c == '+') {
            negative = c == '-';
            c = read_char_raw();
        }

        long double result = 0;
        while ('0' <= c && c <= '9') {
            result = result * 10 + (c - '0');
            c = read_char_raw();
        }
        if (c == '.') {
            long double place = 0.1L;
            c = read_char_raw();
            while ('0' <= c && c <= '9') {
                result += (c - '0') * place;
                place *= 0.1L;
                c = read_char_raw();
            }
        }
        if (c == 'e' || c == 'E') {
            c = read_char_raw();
            bool exponent_negative = false;
            if (c == '-' || c == '+') {
                exponent_negative = c == '-';
                c = read_char_raw();
            }
            int exponent = 0;
            while ('0' <= c && c <= '9') {
                exponent = exponent * 10 + (c - '0');
                c = read_char_raw();
            }
            long double scale = 1;
            long double power = 10;
            while (exponent > 0) {
                if (exponent & 1) scale *= power;
                power *= power;
                exponent >>= 1;
            }
            result = exponent_negative ? result / scale : result * scale;
        }
        value = static_cast<T>(negative ? -result : result);
        return true;
    }

    template <class T>
    std::enable_if_t<
        internal::has_val_method_v<T>
            && !internal::is_integral_v<T>
            && !internal::is_range_v<T>,
        bool
    >
    read(T& value) {
        long long x;
        if (!read(x)) return false;
        if constexpr (internal::has_static_mod_raw_v<T>) {
            if (x >= 0 && uint64_t(x) < uint64_t(T::mod())) {
                value = T::raw(uint32_t(x));
            } else {
                value = T(x);
            }
        } else {
            value = T(x);
        }
        return true;
    }

    template <class First, class Second>
    bool read(std::pair<First, Second>& value) {
        if (!read(value.first)) return false;
        return read(value.second);
    }

    template <class Range>
    std::enable_if_t<
        internal::is_range_v<Range>
            && !internal::is_string_like_v<Range>,
        bool
    >
    read(Range& range) {
        using StoredValue = internal::range_stored_value_t<Range>;
        constexpr bool nested = internal::is_range_v<StoredValue>
                                && !internal::is_string_like_v<StoredValue>;

        for (auto&& value : range) {
            if constexpr (std::is_same_v<StoredValue, bool> && !nested) {
                bool x;
                if (!read(x)) return false;
                value = x;
            } else {
                if (!read(value)) return false;
            }
        }
        return true;
    }

    template <class First, class Second, class... Rest>
    bool read(First& first, Second& second, Rest&... rest) {
        if (!read(first)) return false;
        return read(second, rest...);
    }

    template <class T>
    FastInput& operator>>(T& value) {
        if (!read(value)) std::abort();
        return *this;
    }
};

struct FastOutput {
    static constexpr int buffer_size = 1 << 20;

   private:
    inline static const auto digit_quads = [] {
        std::array<char, 40000> result{};
        for (int i = 0; i < 10000; i++) {
            int value = i;
            for (int j = 3; j >= 0; j--) {
                result[4 * i + j] = char('0' + value % 10);
                value /= 10;
            }
        }
        return result;
    }();

    std::FILE* _stream;
    char _buffer[buffer_size];
    int _position;
    int _precision;
    std::chars_format _float_format;
    char _range_separator;
    std::string* _capture = nullptr;

    template <class T>
    std::string format_cell(const T& value) {
        std::string result;
        struct CaptureGuard {
            std::string*& target;
            std::string* previous;
            ~CaptureGuard() { target = previous; }
        } guard{_capture, _capture};
        _capture = &result;
        write(value);
        return result;
    }

    template <class Matrix>
    void write_aligned_matrix(const Matrix& matrix) {
        std::vector<std::vector<std::string>> rows;
        std::vector<std::size_t> widths;
        for (const auto& row : matrix) {
            auto& cells = rows.emplace_back();
            std::size_t column = 0;
            for (const auto& value : row) {
                cells.push_back(format_cell(value));
                if (column == widths.size()) widths.push_back(0);
                widths[column] = std::max(widths[column], cells.back().size());
                ++column;
            }
        }
        bool first = true;
        for (const auto& row : rows) {
            if (!first) write_char('\n');
            first = false;
            for (std::size_t column = 0; column < row.size(); ++column) {
                if (column != 0) write_char(_range_separator);
                for (std::size_t padding = row[column].size();
                     padding < widths[column]; ++padding) {
                    write_char(' ');
                }
                write(row[column]);
            }
        }
    }

   public:
    explicit FastOutput(std::FILE* stream = stdout)
        : _stream(stream),
          _position(0),
          _precision(6),
          _float_format(std::chars_format::general),
          _range_separator(' ') {
        if (_stream == stdout
            && internal::standard_output_instance == nullptr) {
            internal::standard_output_instance = this;
        }
    }

    FastOutput(const FastOutput&) = delete;
    FastOutput& operator=(const FastOutput&) = delete;

    ~FastOutput() {
        flush();
        if (internal::standard_output_instance == this) {
            internal::standard_output_instance = nullptr;
        }
    }

    void flush() {
        if (_position != 0) {
            std::fwrite(_buffer, 1, _position, _stream);
            _position = 0;
        }
        std::fflush(_stream);
    }

    void write_char(char c) {
        if (_capture != nullptr) {
            _capture->push_back(c);
            return;
        }
        if (_position == buffer_size) flush();
        _buffer[_position++] = c;
    }

    void write(const char* s) {
        while (*s != '\0') write_char(*s++);
    }

    void write(const std::string& s) {
        if (_capture != nullptr) {
            _capture->append(s);
            return;
        }
        std::size_t position = 0;
        while (position < s.size()) {
            if (_position == buffer_size) flush();
            const std::size_t copied =
                std::min<std::size_t>(buffer_size - _position, s.size() - position);
            std::memcpy(_buffer + _position, s.data() + position, copied);
            _position += int(copied);
            position += copied;
        }
    }

    void write(char c) {
        write_char(c);
    }

    void write(bool value) {
        write_char(value ? '1' : '0');
    }

    template <class T>
    std::enable_if_t<std::is_floating_point_v<T>>
    write(T value) {
        char digits[128];
        auto [end, error] = std::to_chars(
            digits,
            digits + sizeof(digits),
            value,
            _float_format,
            _precision
        );
        if (error != std::errc()) std::abort();
        for (const char* pointer = digits; pointer != end; pointer++) {
            write_char(*pointer);
        }
    }

    template <class T>
    std::enable_if_t<
        internal::is_integral_v<T>
            && !std::is_same_v<std::remove_cv_t<T>, bool>
            && !std::is_same_v<std::remove_cv_t<T>, char>
    >
    write(T value) {
        using Raw = std::remove_cv_t<T>;
        using Unsigned = internal::make_unsigned_t<Raw>;

        Unsigned magnitude;
        if constexpr (internal::is_signed_v<Raw>) {
            if (value < 0) {
                write_char('-');
                magnitude = Unsigned(0) - Unsigned(value);
            } else {
                magnitude = Unsigned(value);
            }
        } else {
            magnitude = value;
        }

        if (magnitude == 0) {
            write_char('0');
            return;
        }

        unsigned chunks[16];
        int count = 0;
        while (magnitude >= 10000) {
            const Unsigned quotient = magnitude / 10000;
            chunks[count++] = unsigned(magnitude - quotient * 10000);
            magnitude = quotient;
        }
        if (_capture == nullptr && _position > buffer_size - 64) flush();
        char captured[64];
        char* const begin = _capture != nullptr ? captured : _buffer + _position;
        char* destination = begin;
        const unsigned leading = unsigned(magnitude);
        const char* first = digit_quads.data() + 4 * leading;
        int skip = leading < 10 ? 3 : leading < 100 ? 2 : leading < 1000 ? 1 : 0;
        for (; skip < 4; skip++) *destination++ = first[skip];
        while (count--) {
            const char* digits = digit_quads.data() + 4 * chunks[count];
            std::memcpy(destination, digits, 4);
            destination += 4;
        }
        if (_capture != nullptr) {
            _capture->append(begin, destination - begin);
        } else {
            _position += int(destination - begin);
        }
    }

    template <class T>
    std::enable_if_t<
        internal::has_val_method_v<T>
            && !internal::is_integral_v<T>
            && !internal::is_range_v<T>
    >
    write(const T& value) {
        write(value.val());
    }

    template <class First, class Second>
    void write(const std::pair<First, Second>& value) {
        write(value.first);
        write_char(' ');
        write(value.second);
    }

    template <class Range>
    std::enable_if_t<
        internal::is_range_v<Range>
            && !internal::is_string_like_v<Range>
    >
    write(const Range& range) {
        using StoredValue = internal::range_stored_value_t<const Range>;
        constexpr bool nested = internal::is_range_v<StoredValue>
                                && !internal::is_string_like_v<StoredValue>;

        bool first = true;
        for (const auto& value : range) {
            if (!first) write_char(nested ? '\n' : _range_separator);
            first = false;
            if constexpr (std::is_same_v<StoredValue, bool> && !nested) {
                write(static_cast<bool>(value));
            } else {
                write(value);
            }
        }
    }

    template <class First, class... Rest>
    void print(const First& first, const Rest&... rest) {
        write(first);
        ((write_char(' '), write(rest)), ...);
    }

    void println() {
        write_char('\n');
    }

    void set_precision(int precision) {
        _precision = precision;
    }

    void set_fixed(int precision = 6) {
        _float_format = std::chars_format::fixed;
        _precision = precision;
    }

    void set_general(int precision = 6) {
        _float_format = std::chars_format::general;
        _precision = precision;
    }

    void set_range_separator(char separator) {
        _range_separator = separator;
    }

    template <class Matrix>
    void write_aligned(const Matrix& matrix) {
        using Row = internal::range_stored_value_t<const Matrix>;
        using Cell = internal::range_stored_value_t<const Row>;
        static_assert(internal::is_range_v<Row> && !internal::is_string_like_v<Row>,
                      "write_aligned requires a two-dimensional range");
        static_assert(!internal::is_range_v<Cell> || internal::is_string_like_v<Cell>,
                      "write_aligned requires scalar cells");
        write_aligned_matrix(matrix);
    }

    template <class Matrix>
    void println_aligned(const Matrix& matrix) {
        write_aligned(matrix);
        write_char('\n');
    }

    template <class... Args>
    void println(const Args&... args) {
        print(args...);
        write_char('\n');
    }

    template <class T>
    FastOutput& operator<<(const T& value) {
        write(value);
        return *this;
    }
};

}  // namespace utilities
}  // namespace m1une


#line 7 "verify/geometry/circle_relation.test.cpp"

int main() {
    m1une::utilities::FastInput fast_input;
    m1une::utilities::FastOutput fast_output;
    using namespace m1une::geometry;

    Circle<long long> first;
    Circle<long long> second;
    fast_input >> first.center.x >> first.center.y >> first.radius;
    fast_input >> second.center.x >> second.center.y >> second.radius;

    int answer = -1;
    switch (circle_relation(first, second)) {
        case CircleRelation::Separate:
            answer = 4;
            break;
        case CircleRelation::ExternallyTangent:
            answer = 3;
            break;
        case CircleRelation::Intersecting:
            answer = 2;
            break;
        case CircleRelation::InternallyTangent:
            answer = 1;
            break;
        case CircleRelation::Contained:
            answer = 0;
            break;
        case CircleRelation::Coincident:
            assert(false);
    }
    fast_output << answer << '\n';
}

Back to top page