geometry.py

import bisect
import enum
import itertools
import math
from collections.abc import Callable, Iterable, Sequence
from typing import TypeAlias, Literal

Point: TypeAlias = Sequence[int]
Vector: TypeAlias = Sequence[int]
Polygon: TypeAlias = Sequence[Point]

# N twice_of_polygon_area
# I {"version": "0.1"}
def twice_of_polygon_area(polygon: Polygon) -> int:
    """Computes twice of area of given polygon in O(n)."""
    signed_area = sum(
        (p1[0] - p2[0]) * (p1[1] + p2[1])
        for p1, p2 in itertools.pairwise([*polygon, polygon[0]])
    )
    return abs(signed_area)

• TODO

# N lattice_point_in_polygon
# I {"version": "0.1"}
def lattice_point_in_polygon(polygon: Polygon) -> tuple[int, int]:
    """Counts lattice points at boundary and interior of polygon in O(n).

    Args:
        polygon: A simple polygon.
    Returns:
        A tuple of (I, B).
        - I: the number of lattice points lying strictly inside the polygon.
        - B: the number of lattice points lying on polygon sides.
    """
    twice_area = boundary_point_count = 0
    for p1, p2 in itertools.pairwise([*polygon, polygon[0]]):
        twice_area += (p1[0] - p2[0]) * (p1[1] + p2[1])
        boundary_point_count += math.gcd(p1[0] - p2[0], p1[1] - p2[1])
    interior_point_count = (abs(twice_area) - boundary_point_count) // 2 + 1
    return interior_point_count, boundary_point_count

• TODO