Day 022-Q2 | 凸多面体の格子点計数（Pick + Ehrhart）

問題

2次元平面上に $N$ 頂点の凸多角形が与えられる（全頂点は格子点）。整数 $t$ が $Q$ 個与えられる。各 $t$ に対して、元の凸多角形を $t$ 倍に拡大した多角形（各頂点座標を $t$ 倍）の内部および境界上にある格子点の総数を答えよ。

入力形式

N
x_1 y_1
x_2 y_2
...
x_N y_N
Q
t_1
t_2
...
t_Q

制約

$3 \leq N \leq 100$

$-10^4 \leq x_i, y_i \leq 10^4$

$1 \leq Q \leq 10^5$

$1 \leq t_i \leq 10^6$

多角形は凸かつ反時計回りに与えられる

入出力例

入力例 1

出力例 1

正方形 $[0,2]^2$ の格子点数は $3^2=9$。$t$ 倍すると $(2t+1)^2 = 4t^2+4t+1$。

ヒント (段階的開示)

ヒント1: 方向性

Pick の定理と Ehrhart 多項式を使う。凸多角形の格子点数は $t$ の2次多項式（Ehrhart 多項式）で表せる。

ヒント2: アプローチ

Pick の定理: 格子点多角形において $A = I + \frac{B}{2} - 1$（$A$ = 面積、$I$ = 内部格子点数、$B$ = 境界格子点数）。Ehrhart 多項式: 凸多角形 $P$ の $t$ 倍拡大の格子点数は $L(P, t) = A \cdot t^2 + \frac{B}{2} \cdot t + 1$。

ヒント3: 誘導

from math import gcd

def compute_area2(vertices):
    """Shoelace formula, return 2*Area (integer)"""
    n = len(vertices)
    s = 0
    for i in range(n):
        x1, y1 = vertices[i]
        x2, y2 = vertices[(i+1) % n]
        s += x1 * y2 - x2 * y1
    return abs(s)  # = 2 * Area

def boundary_points(vertices):
    """Count lattice points on boundary"""
    n = len(vertices)
    B = 0
    for i in range(n):
        x1, y1 = vertices[i]
        x2, y2 = vertices[(i+1) % n]
        B += gcd(abs(x2 - x1), abs(y2 - y1))
    return B

# Ehrhart: L(t) = A * t^2 + (B/2) * t + 1
# = (2A * t^2 + B * t + 2) / 2

模範解答 (Python)

import sys
from math import gcd
input = sys.stdin.readline

def solve():
    N = int(input())
    vertices = []
    for _ in range(N):
        x, y = map(int, input().split())
        vertices.append((x, y))

    # Compute 2 * Area using Shoelace formula
    area2 = 0
    for i in range(N):
        x1, y1 = vertices[i]
        x2, y2 = vertices[(i+1) % N]
        area2 += x1 * y2 - x2 * y1
    area2 = abs(area2)  # This is 2*A (integer)

    # Compute boundary points B
    B = 0
    for i in range(N):
        x1, y1 = vertices[i]
        x2, y2 = vertices[(i+1) % N]
        B += gcd(abs(x2 - x1), abs(y2 - y1))

    # Ehrhart polynomial: L(t) = A * t^2 + (B/2) * t + 1
    # = (area2 * t^2 + B * t + 2) / 2

    Q = int(input())
    results = []
    for _ in range(Q):
        t = int(input())
        numerator = area2 * t * t + B * t + 2
        results.append(numerator // 2)

    print('\n'.join(map(str, results)))

solve()

Step-by-Step 解説

1Pick の定理の理解
格子点多角形の面積 $A$、内部格子点数 $I$、境界格子点数 $B$ の間には $A = I + \frac{B}{2} - 1 \implies I = A - \frac{B}{2} + 1$。全格子点数 $L = I + B = A + \frac{B}{2} + 1$。

2t 倍拡大への適用
元の多角形を $t$ 倍にすると面積: $A_t = A \cdot t^2$、境界格子点数: $B_t = B \cdot t$。よって $L(t) = A_t + \frac{B_t}{2} + 1 = A t^2 + \frac{B}{2} t + 1$。

3整数演算での実装
$2A$（Shoelace 公式の結果は偶数とは限らないが、Pick の定理から $2A$ と $B$ は同パリティ）を計算し、$L(t) = \frac{2A \cdot t^2 + B \cdot t + 2}{2}$ を整数除算で求める。

4境界格子点数の計算
辺 $(x_1, y_1) \to (x_2, y_2)$ 上の格子点数（端点を1つ含む）は $\gcd(|dx|, |dy|)$。

よくあるミス

ミス	原因	正しい書き方
Shoelace の結果に `abs` を忘れる	反時計回りで負になる場合あり	`area2 = abs(shoelace_result)`
境界点を辺ごとに `gcd` で計算しない	単純に $\|dx\| + \|dy\|$ では誤り	`gcd(abs(dx), abs(dy))`
$L(t)$ の整数性を確認しない	$2A$ と $B$ は同パリティのため常に整数	整数除算 `// 2` で OK
$t=0$ のケースを忘れる	$L(0) = 1$（原点のみ）	公式に代入して確認

次のステップ

発展問題: 3次元格子多面体の格子点数を Ehrhart 多項式の3次版で解く
さらに難しい: 非凸多角形・穴あき多角形への Pick の定理の一般化

自己評価

完全理解おおむね理解要復習

Day 022-Q2 — 凸多面体の格子点計数（Pick の定理 + Ehrhart 多項式）

問題