格点计数

What · 是什么

格点计数问题：统计线段上、直线下区域、多边形内（或内加边界）的整点（整数坐标点）数量。三条主线：① 线段上的整点：端点 (x1,y1)-(x2,y2) 间整点数 = gcd(|x2-x1|,|y2-y1|)+1；② 整点多边形：皮克定理反解内部点数 i = (A2 - b + 2)/2，其中 A2 是两倍面积（叉积和），b 是边界整点数（各边 gcd 之和）；③ 一般（非整点顶点）多边形：把每条边看作直线 y=k·x+b，用 floor sum Σ floor((a·x+b)/m) 的类欧几里得递推 O(log n) 求出直线下整点数，再按边方向带符号累加（类似梯形积分）。核心引擎是 floor_sum。

Why · 为什么

How · 实现

伪代码

# 线段上整点数（含端点）
on_segment(a, b) = gcd(|b.x-a.x|, |b.y-a.y|) + 1

# floor_sum: Σ_{x=0}^{n-1} floor((a*x+b)/m)，a,b≥0，O(log n)
def floor_sum(n, m, a, b):
    ans = 0
    while True:
        if a >= m: ans += (n-1)*n*(a//m)//2; a %= m
        if b >= m: ans += n*(b//m); b %= m
        y_max = a*n + b
        if y_max < m: break
        n, b = y_max // m, y_max % m
        m, a = a, m
    return ans

# 整点多边形内部点数（皮克定理）
def polygon_interior(poly):
    A2 = |Σ x_i*y_{i+1} - x_{i+1}*y_i|          # 两倍面积
    b  = Σ gcd(|dx_i|, |dy_i|)                    # 边界整点数
    return (A2 - b + 2) // 2

Python 实现

# -*- coding: utf-8 -*-
import math


def floor_sum(n, m, a, b):
    """Σ_{x=0}^{n-1} floor((a*x + b) / m)。要求 a,b>=0, m>0。O(log n)。
    这就是'类欧几里得'的核心递推。
    """
    ans = 0
    while True:
        if a >= m:
            ans += (n - 1) * n * (a // m) // 2
            a %= m
        if b >= m:
            ans += n * (b // m)
            b %= m
        y_max = a * n + b
        if y_max < m:
            break
        n = y_max // m
        b = y_max % m
        m, a = a, m
    return ans


def floor_sum_signed(n, m, a, b):
    """与 floor_sum 相同但允许 a、b 为负（先对 a 取模归并到 [0,m)，再平移 b）。"""
    ans = 0
    q, r = divmod(a, m)          # a = q*m + r, 0 <= r < m
    if q != 0:
        ans += q * n * (n - 1) // 2
        a = r
    if b < 0:
        k = (-b + m - 1) // m
        ans -= k * n
        b += k * m
    return ans + floor_sum(n, m, a, b)


def lattice_on_segment(a, b):
    """线段 a→b 上的整点数（含两端）。"""
    return math.gcd(abs(b[0]-a[0]), abs(b[1]-a[1])) + 1


def polygon_interior_points(poly):
    """整点多边形内部整点数（皮克定理）。顶点必须都是整点。"""
    n = len(poly)
    A2 = 0
    b = 0
    for i in range(n):
        x1, y1 = poly[i]
        x2, y2 = poly[(i+1) % n]
        A2 += x1*y2 - x2*y1
        b += math.gcd(abs(x2-x1), abs(y2-y1))
    A2 = abs(A2)
    return (A2 - b + 2) // 2


def polygon_boundary_points(poly):
    """整点多边形边界整点数。"""
    n = len(poly)
    return sum(math.gcd(abs(poly[(i+1) % n][0]-poly[i][0]),
                        abs(poly[(i+1) % n][1]-poly[i][1])) for i in range(n))


if __name__ == '__main__':
    import random
    # floor_sum 对拍暴力
    for _ in range(1000):
        n = random.randint(1, 40)
        m = random.randint(1, 50)
        a = random.randint(0, 40)
        b = random.randint(0, 50)
        bf = sum((a*i + b) // m for i in range(n))
        assert floor_sum(n, m, a, b) == bf, (n, m, a, b, floor_sum(n, m, a, b), bf)
    # floor_sum_signed 对拍（允许负 a,b）
    for _ in range(1000):
        n = random.randint(1, 40)
        m = random.randint(1, 50)
        a = random.randint(-30, 30)
        b = random.randint(-40, 40)
        bf = sum((a*i + b) // m for i in range(n))
        assert floor_sum_signed(n, m, a, b) == bf, (n, m, a, b, floor_sum_signed(n, m, a, b), bf)
    # 线段整点数
    assert lattice_on_segment((0, 0), (6, 9)) == 4    # gcd(6,9)=3 → 4 个点
    assert lattice_on_segment((0, 0), (0, 5)) == 6
    assert lattice_on_segment((0, 0), (1, 1)) == 2
    # 皮克定理与暴力对拍
    def brute_interior(poly):
        xs = [p[0] for p in poly]
        ys = [p[1] for p in poly]
        cnt = 0
        for x in range(min(xs), max(xs)+1):
            for y in range(min(ys), max(ys)+1):
                n = len(poly)
                onb = False
                for i in range(n):
                    x1, y1 = poly[i]
                    x2, y2 = poly[(i+1) % n]
                    if (y1-y)*(x2-x) == (y2-y)*(x1-x) and min(x1,x2) <= x <= max(x1,x2) and min(y1,y2) <= y <= max(y1,y2):
                        onb = True
                if onb:
                    continue
                inside = False
                for i in range(n):
                    x1, y1 = poly[i]
                    x2, y2 = poly[(i+1) % n]
                    if (y1 > y) != (y2 > y):
                        xi = x1 + (x2-x1)*(y-y1)/(y2-y1)
                        if x < xi:
                            inside = not inside
                if inside:
                    cnt += 1
        return cnt
    polys = [
        [(0, 0), (5, 0), (5, 3), (0, 3)],
        [(0, 0), (4, 0), (4, 4), (0, 4)],
        [(0, 0), (3, 1), (4, 4), (1, 3)],
        [(0, 0), (2, 0), (2, 2), (0, 2)],
    ]
    for poly in polys:
        assert polygon_interior_points(poly) == brute_interior(poly), (poly, polygon_interior_points(poly), brute_interior(poly))
    print('lattice-points all tests passed')

易错点

• floor_sum 的 a、b 必须非负，负输入要先归一化
• 非整点多边形逐边积分时端点取整方向写反会差 1
• 边界整点归属：内部点数不含边界（皮克定理 i 的定义）
• 自交多边形不适用
• 线段上整点数公式是 gcd+1（含两端），不要漏 +1 或重复计端点

例题

信源

• CP-Algorithms✓ https://cp-algorithms.com/geometry/lattice-points.html
• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/geometry/pick.md