m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

View on GitHub

:heavy_check_mark: Geometry Bundle
(geometry/all.hpp)

Overview

geometry/all.hpp includes the complete 2D geometry module.

Included Headers

Header Contents
geometry/angle_sort.hpp Atan-free counterclockwise angle sorting around an arbitrary origin.
geometry/circle_coverage_areas.hpp Areas covered by exactly $k$ enclosed circles for every $k$ in $O(N^2\log N)$.
geometry/circle_union_area.hpp Union area of enclosed circles in $O(N^2\log N)$.
geometry/point.hpp Points, vectors, dot/cross products, exact orientation, distance, centroid, and rotation.
geometry/closest_pair.hpp Euclidean closest pair with original indices in $O(N\log N)$.
geometry/convex_decomposition.hpp Hertel–Mehlhorn approximate and Keil–Snoeyink minimum convex decompositions of a simple polygon.
geometry/convex_hull.hpp Monotone-chain convex hull with optional boundary-collinear points.
geometry/convex_layers.hpp Onion decomposition into successive convex-hull boundaries in $O(N\log^2 N)$.
geometry/convex_polygon.hpp Normalized convex-polygon queries, centroid, cuts, diameter, intersections, distance, and triangulation.
geometry/count_points_in_triangle.hpp Preprocessed strict point counts for indexed triangle queries in $O(1)$ per query.
geometry/delaunay_triangulation.hpp Exact Delaunay edges and counterclockwise triangular faces for integral points in $O(N\log N)$.
geometry/euclidean_mst.hpp Euclidean minimum spanning tree for integral points in $O(N\log N)$.
geometry/farthest_pair.hpp Euclidean farthest pair with original indices in $O(N\log N)$.
geometry/half_plane_intersection.hpp Bounded intersection polygon of directed closed half-planes in $O(N\log N)$.
geometry/lattice_point_count.hpp Exact lattice-point counting in a bounded intersection of integer linear inequalities.
geometry/manhattan_mst.hpp Manhattan minimum spanning tree for integral points in $O(N\log N)$.
geometry/manhattan_segment_intersections.hpp Counts or enumerates intersections of axis-aligned integral segments.
geometry/minimum_enclosing_circle.hpp Randomized linear-time minimum enclosing circle with support indices.
geometry/minkowski_sum.hpp Linear-time Minkowski sum of two ordered convex polygons.
geometry/linear.hpp Lines, segments, rays, classified linear intersections, projection, reflection, centroids, and distances.
geometry/perpendicular_bisector.hpp Floating-point and lattice-point perpendicular bisectors of two distinct points.
geometry/rectangle_union_area.hpp Exact union area of axis-aligned rectangles in $O(N\log N)$.
geometry/steiner_convex_decomposition.hpp Floating-point Steiner convex decomposition with an exact union and a strict 2-approximation piece count.
geometry/voronoi_diagram.hpp Exact-topology Euclidean Voronoi diagrams with segments, rays, lines, and per-site boundary edges in $O(N\log N)$.
geometry/polygon.hpp Filled-or-boundary polygons, path clipping, area, centroids, triangulation, containment, intersections, and distance.
geometry/circle.hpp Filled-or-boundary circles, relations, intersections, closest points, areas, tangents, and reflection.

Integral predicates promote to signed 128-bit arithmetic. Constructions that may be non-integral return Point<long double>.

Core floating-point point, line, segment, and ray predicates use a dimensionless scale-aware epsilon. Uniformly scaling a complete configuration does not change their orientation, direction, containment, or intersection classification. See the individual point, line, and ray pages for the exact tolerance semantics.

Centroid overloads

The bounded geometry types share the free function name centroid:

template <Coordinate T>
Point<long double> centroid(const Point<T>& point);

template <Coordinate T>
Point<long double> centroid(const Segment<T>& segment);

template <Coordinate T>
Point<long double> centroid(
    const std::array<Point<T>, 3>& triangle
);

template <Coordinate T>
Point<long double> centroid(const Circle<T>& circle);

template <Coordinate T>
std::optional<Point<long double>> centroid(
    const std::vector<Point<T>>& polygon,
    long double eps = 1e-12L
);

template <Coordinate T>
std::optional<Point<long double>> centroid(
    const Polygon<T>& polygon,
    long double eps = 1e-12L
);

template <Coordinate T>
std::optional<Point<long double>> centroid(
    const ConvexPolygon<T>& polygon,
    long double eps = 1e-12L
);

Point, segment, triangle, and circle centroids take $O(1)$ time. Polygon centroids take $O(N)$ and use uniform filled-area density. The vector overload accepts any simple polygon, including concave and clockwise boundaries. It returns nullopt for zero signed area; the convex query-object overload has the same behavior for empty, point, or segment objects.

Infinite lines and rays are unbounded, so they intentionally have no centroid overload.

Depends on

Verified with

Code

#ifndef M1UNE_GEOMETRY_ALL_HPP
#define M1UNE_GEOMETRY_ALL_HPP 1

#include "angle_sort.hpp"
#include "circle.hpp"
#include "circle_coverage_areas.hpp"
#include "circle_union_area.hpp"
#include "closest_pair.hpp"
#include "convex_decomposition.hpp"
#include "convex_hull.hpp"
#include "convex_layers.hpp"
#include "convex_polygon.hpp"
#include "count_points_in_triangle.hpp"
#include "delaunay_triangulation.hpp"
#include "euclidean_mst.hpp"
#include "farthest_pair.hpp"
#include "half_plane_intersection.hpp"
#include "lattice_point_count.hpp"
#include "linear.hpp"
#include "manhattan_mst.hpp"
#include "manhattan_segment_intersections.hpp"
#include "minimum_enclosing_circle.hpp"
#include "minkowski_sum.hpp"
#include "perpendicular_bisector.hpp"
#include "point.hpp"
#include "polygon.hpp"
#include "rectangle_union_area.hpp"
#include "steiner_convex_decomposition.hpp"
#include "voronoi_diagram.hpp"

#endif  // M1UNE_GEOMETRY_ALL_HPP
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 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