Competitive Programming Library

This project contains my competitive programming library, examples, and solutions.

Library

Algebra

• Greatest Common Divisor
• Least Common Multiple
• Binary Exponentiation
• Prime Factorization
• Binomial Coefficients
• Extended Euclidean Algorithm

Geometry (2D)

• Basic Operations
• Projection, Rejection
• CCW
• Line
  • Orthogonal
  • Parallel
• Intersection
  • Line-Point
  • Segment-Point
  • Line-Line
  • Segment-Segment
  • Line-Segment (w/o point)
  • Circle-Circle
  • Circle-Line
• Distance
  • Line-Point
  • Segment-Point
  • Line-Line
  • Segment-Segment
  • Line-Segment
• Polygon
  • Area
  • Convex Check
  • Containment (ON, IN, OUT)
  • Convex Hull
  • Convex Diameter
• Circle
  • Tangent Line
    • Circle-Point
    • Circle-Circle
• Line Sweep
  • Distance of the Closest Pair
  • Segment Intersections in Manhattan Geometry
  • Area of Union Rectangles

Geometry (3D)

• Basic Operations
• Projection, Rejection

Data Structures

• Disjoint Set Union
• Binary Indexed Tree
• MinMax Queue
• MinMax Stack
• Randomized Heap
• Segment Tree
• Sqrt Decomposition
• Sparse Table
• Disjoint Sparse Table
• Treap
• Implicit Treap
• kD Tree (n-dimensional)

Tree

• Diameter
• Euler Tour
• Heavy Light Decomposition
• Height
• Lowest Common Ancestor

Graph

• Articulation Points
• Bridges
• Topological Sort
• Strongly Connected Components
• Single-Source Shortest Path
  • Dijkstra
    Support Only Positive Weights
  • Bellman-Ford
    Support Negative Weights
  • SPFA
    Support Negative Weights
• All-Pairs Shortest Path
  • Floyd-Warshall
• Bipartite
  • Bipartite Check
  • Bipartite Maximum Matching
• Cycle
  • Finding Cycle
  • Finding Negative Cycle
    • Floyed-Warshall
    • Bellman-Ford
• Minimum Spanning Tree
• Minimum Cost Arborescence
• Maximum Flow
  • Dinic
  • Edmonds-Karp
  • MPM
  • Push Relabel (Generic)
  • Push Relabel (Highest)
• Minimum Cut
• Minimum Cost Flow

String

• Z Algorithm

Utilities

• Binary Search
• Two Pointers
  "しゃくとり法" in Japanese
• BigInt
• Dice
• modint

How to provision development environment

Use Visual Studio Remote Containers*

How to build library and examples

See lib/README.md

References

• cplusplus.com

Learning sites

• Topcoder Competitive Programming Tutorials
• E-Maxx Algorithms in English
• Top 10 Algorithms and Data Structures for Competitive Programming | GeekforGeeks
• SecondThread
• アルゴリズムロジック
• 各種アルゴリズムの C++ による実装

Tips

GCC Compiler Flags

It would be better to use the following compiler flags. In the Visual Studio Code Remote Container environment, the flags are used as default by the command alias. See Dockerfile.

• -D_GLIBCXX_DEBUG
  See Macros

• -fsanitize=undefined
  See Program Instrumentation Options