Minimal, copy-paste Python for combinatorics (nCk mod P) and 2D geometry primitives (cross product, point on segment).

Cross Product — determines turn direction A B C cross(A,B,C) = (B-A) × (C-A) > 0 → counter-clockwise (left turn) | < 0 → clockwise | = 0 → collinear Used for: convex hull, polygon area, point-in-polygon, segment intersection

Contents

Combinatorics (nCk mod P)

MOD = 1_000_000_007
N = 200_000

fact = [1] * (N + 1)
invfact = [1] * (N + 1)


def modexp(a: int, e: int) -> int:
    r = 1
    a %= MOD
    while e > 0:
        if e & 1:
            r = (r * a) % MOD
        a = (a * a) % MOD
        e >>= 1
    return r


def init_comb() -> None:
    for i in range(1, N + 1):
        fact[i] = (fact[i - 1] * i) % MOD
    invfact[N] = modexp(fact[N], MOD - 2)
    for i in range(N, 0, -1):
        invfact[i - 1] = (invfact[i] * i) % MOD


def nCk(n: int, k: int) -> int:
    if k < 0 or k > n:
        return 0
    return fact[n] * invfact[k] % MOD * invfact[n - k] % MOD
ID Title Link Solution
62 Unique Paths Link Solution
172 Factorial Trailing Zeroes Link -

Geometry Primitives (2D)

from dataclasses import dataclass


@dataclass
class P:
    x: int
    y: int


def cross(a: P, b: P, c: P) -> int:
    # cross((b-a), (c-a))
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)


def on_segment(a: P, b: P, c: P) -> bool:
    # c lies on segment ab
    return (
        cross(a, b, c) == 0
        and min(a.x, b.x) <= c.x <= max(a.x, b.x)
        and min(a.y, b.y) <= c.y <= max(a.y, b.y)
    )
ID Title Link Solution
149 Max Points on a Line Link -
223 Rectangle Area Link -
1344 Angle Between Hands of a Clock Link Solution

More templates