verify/geometry/geometry_algorithms.test.cpp

• View this file on GitHub
• Last update: 2026-10-06 02:48:54+09:00
• Problem: https://judge.yosupo.jp/problem/aplusb

Depends on

• DSU (Disjoint Set Union) (ds/dsu/dsu.hpp)
• Fenwick Tree (Binary Indexed Tree) (ds/range_query/fenwick_tree.hpp)
• Geometry Bundle (geometry/all.hpp)
• Angle Sort (geometry/angle_sort.hpp)
• Circles (geometry/circle.hpp)
• Circle Coverage Areas (geometry/circle_coverage_areas.hpp)
• Area of Union of Circles (geometry/circle_union_area.hpp)
• Closest Pair of Points (geometry/closest_pair.hpp)
• Convex Decomposition (geometry/convex_decomposition.hpp)
• Convex Hull (geometry/convex_hull.hpp)
• Convex Layers (geometry/convex_layers.hpp)
• Convex Polygons (geometry/convex_polygon.hpp)
• Count Points in Triangle (geometry/count_points_in_triangle.hpp)
• Delaunay Triangulation (geometry/delaunay_triangulation.hpp)
• geometry/detail/convex_polygon_normalize.hpp
• geometry/detail/floating_predicate.hpp
• Euclidean Minimum Spanning Tree (geometry/euclidean_mst.hpp)
• Farthest Pair of Points (geometry/farthest_pair.hpp)
• Half-Plane Intersection (geometry/half_plane_intersection.hpp)
• Lattice-Point Count (geometry/lattice_point_count.hpp)
• Linear Objects (geometry/linear.hpp)
• Manhattan Minimum Spanning Tree (geometry/manhattan_mst.hpp)
• Manhattan Segment Intersections (geometry/manhattan_segment_intersections.hpp)
• Minimum Enclosing Circle (geometry/minimum_enclosing_circle.hpp)
• Minkowski Sum (geometry/minkowski_sum.hpp)
• Perpendicular Bisector (geometry/perpendicular_bisector.hpp)
• 2D Point and Predicates (geometry/point.hpp)
• 2D Point and Predicates (geometry/point.hpp)
• Polygons (geometry/polygon.hpp)
• Area of Union of Rectangles (geometry/rectangle_union_area.hpp)
• Steiner Convex Decomposition (geometry/steiner_convex_decomposition.hpp)
• Voronoi Diagram (geometry/voronoi_diagram.hpp)
• Convolution (math/fps/convolution.hpp)
• math/fps/internal/ntt998_faster.hpp
• ModInt (math/modint.hpp)
• BigInt (utilities/bigint.hpp)
• utilities/detail/fixed_int.hpp
• Fast IO (utilities/fast_io.hpp)
• Int256 (utilities/int256.hpp)
• Int512 (utilities/int512.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"

#include "../../geometry/all.hpp"

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdint>
#include "../../utilities/fast_io.hpp"
#include <vector>

namespace {

bool close(long double a, long double b) {
    return std::fabs(a - b) <= 1e-10L;
}

void test_basic() {
    using namespace m1une::geometry;
    using P = Point<long long>;

    P a(0, 0);
    P b(3, 0);
    P c(1, 2);
    assert(cross(a, b, c) == 6);
    assert(orientation(a, b, c) == 1);
    assert(orientation(a, c, b) == -1);
    assert(collinear(a, P(1, 0), b));

    P division_start(0, 2);
    P division_end(10, 12);
    Point<long double> internal =
        internal_division_point(division_start, division_end, 2, 3);
    assert(close(internal.x, 4));
    assert(close(internal.y, 6));

    Point<long double> external_after =
        external_division_point(division_start, division_end, 2, 1);
    assert(close(external_after.x, 20));
    assert(close(external_after.y, 22));

    Point<long double> external_before =
        external_division_point(division_start, division_end, 1, 2);
    assert(close(external_before.x, -10));
    assert(close(external_before.y, -8));

    Segment<long long> first;
    first.a = P(0, 0);
    first.b = P(4, 4);
    Segment<long long> second;
    second.a = P(0, 4);
    second.b = P(4, 0);
    assert(intersects(first, second));
    assert(close(distance(first, second), 0));

    Line<long long> horizontal;
    horizontal.a = P(0, 0);
    horizontal.b = P(4, 0);
    [[maybe_unused]] Point<long double> projected = projection(horizontal, P(2, 3));
    assert(close(projected.x, 2));
    assert(close(projected.y, 0));

    Line<long long> diagonal1;
    diagonal1.a = P(0, 0);
    diagonal1.b = P(2, 2);
    Line<long long> diagonal2;
    diagonal2.a = P(0, 2);
    diagonal2.b = P(2, 0);
    const LinearIntersection crossing =
        linear_intersection(diagonal1, diagonal2);
    assert(crossing.kind == LinearIntersectionKind::Point);
    assert(close(crossing.first.x, 1));
    assert(close(crossing.first.y, 1));

    std::vector<P> square;
    square.emplace_back(0, 0);
    square.emplace_back(2, 0);
    square.emplace_back(2, 2);
    square.emplace_back(0, 2);
    assert(polygon_area2(square) == 8);
    assert(point_in_polygon(square, P(1, 1)) == PointInPolygon::Inside);
    assert(point_in_polygon(square, P(0, 1)) == PointInPolygon::Boundary);
    assert(point_in_polygon(square, P(3, 1)) == PointInPolygon::Outside);
    assert(convex_diameter2(square) == 8);

    Circle<long double> circle;
    circle.center = Point<long double>(0, 0);
    circle.radius = 2;
    Line<long double> line;
    line.a = Point<long double>(-3, 0);
    line.b = Point<long double>(3, 0);
    auto intersections = circle_boundary_intersection(circle, line);
    assert(intersections.contact_count == 2);
    assert(close(intersections.contacts[0].point.x, -2));
    assert(close(intersections.contacts[1].point.x, 2));

    Circle<long double> other;
    other.center = Point<long double>(3, 0);
    other.radius = 2;
    assert(circle_relation(circle, other) == CircleRelation::Intersecting);
    auto circle_points = circle_boundary_intersection(circle, other);
    assert(circle_points.contact_count() == 2);
    for (int index = 0; index < circle_points.contact_count(); ++index) {
        const auto& point = circle_points.contacts[index].point;
        assert(close(distance(point, circle.center), circle.radius));
        assert(close(distance(point, other.center), other.radius));
    }

    std::vector<P> collinear_points;
    collinear_points.emplace_back(2, 0);
    collinear_points.emplace_back(0, 0);
    collinear_points.emplace_back(1, 0);
    assert(convex_hull(collinear_points).size() == 2);
    assert(convex_hull(collinear_points, true) == std::vector<P>({P(0, 0), P(1, 0), P(2, 0)}));
}

void test_randomized_hulls() {
    using namespace m1une::geometry;
    using P = Point<long long>;
    std::uint64_t state = 41;
    auto random = [&state]() {
        state ^= state << 7;
        state ^= state >> 9;
        return state;
    };

    for (int trial = 0; trial < 3000; trial++) {
        int n = int(random() % 30);
        std::vector<P> points;
        for (int i = 0; i < n; i++) {
            points.emplace_back(
                static_cast<long long>(random() % 31) - 15,
                static_cast<long long>(random() % 31) - 15
            );
        }
        std::vector<P> hull = convex_hull(points);
        if (hull.size() >= 3) {
            assert(polygon_area2(hull) > 0);
            for (std::size_t i = 0; i < hull.size(); i++) {
                assert(orientation(
                    hull[i],
                    hull[(i + 1) % hull.size()],
                    hull[(i + 2) % hull.size()]
                ) > 0);
            }

            auto expected_diameter = wide_type<long long>(0);
            for (const P& a : hull) {
                for (const P& b : hull) {
                    expected_diameter = std::max(expected_diameter, distance2(a, b));
                }
            }
            assert(convex_diameter2(hull) == expected_diameter);
        }

        for ([[maybe_unused]] const P& point : points) {
            if (hull.size() >= 3) {
                assert(point_in_polygon(hull, point) != PointInPolygon::Outside);
            } else if (hull.size() == 2) {
                Segment<long long> segment;
                segment.a = hull[0];
                segment.b = hull[1];
                assert(on_segment(segment, point));
            } else if (hull.size() == 1) {
                assert(point == hull[0]);
            }
        }
    }
}

}  // namespace

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

    test_basic();
    test_randomized_hulls();

    long long a, b;
    fast_input >> a >> b;
    fast_output << a + b << '\n';
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
  File "/home/runner/.local/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
  File "/home/runner/.local/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 400, in update
    raise BundleErrorAt(path, i + 1, "unable to process #include in #if / #ifdef / #ifndef other than include guards")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: geometry/lattice_point_count.hpp: line 28: unable to process #include in #if / #ifdef / #ifndef other than include guards

Back to top page