Day 073-Q4 — 面積・Shoelace 公式・ピック定理・格子点多角形

問題

$N$ 頂点の単純多角形（頂点は整数座標、自己交差なし）が与えられる。以下を求めよ：

1. 面積: 多角形の面積（整数または半整数）
2. 内部格子点数: 多角形の厳密な内部にある格子点の数（辺上は含まない）
3. 辺上格子点数: 多角形の辺上にある格子点の数（頂点を含む）

入出力例

4
0 0
5 0
5 5
0 5

面積: 25
辺上格子点: 20
内部格子点: 16

3
0 0
4 0
0 3

面積: 6
辺上格子点: 8
内部格子点: 3

概念図: Pick の定理

ヒント

from math import gcd

area2 = 0
for i in range(N):
    x1, y1 = pts[i]; x2, y2 = pts[(i+1)%N]
    area2 += x1*y2 - x2*y1
area2 = abs(area2)

B = sum(gcd(abs(pts[(i+1)%N][0]-pts[i][0]),
           abs(pts[(i+1)%N][1]-pts[i][1])) for i in range(N))

I = (area2 - B + 2) // 2

模範解答

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

def solve():
    N = int(input())
    pts = [tuple(map(int, input().split())) for _ in range(N)]

    # Shoelace 公式で 2*面積 を計算（整数）
    area2 = 0
    for i in range(N):
        x1, y1 = pts[i]
        x2, y2 = pts[(i+1) % N]
        area2 += x1 * y2 - x2 * y1
    area2 = abs(area2)

    # 辺上格子点数 B
    B = 0
    for i in range(N):
        x1, y1 = pts[i]
        x2, y2 = pts[(i+1) % N]
        B += gcd(abs(x2-x1), abs(y2-y1))

    # Pick の定理: I = (2A - B + 2) / 2
    I = (area2 - B + 2) // 2

    if area2 % 2 == 0:
        area_str = str(area2 // 2)
    else:
        area_str = f"{area2 // 2}.5"

    print(f"面積: {area_str}")
    print(f"辺上格子点: {B}")
    print(f"内部格子点: {I}")

solve()

Step-by-Step 解説

Step 1: Shoelace（ガウスの面積）公式

$$2A = \left|\sum_{i=0}^{N-1} (x_i y_{i+1} - x_{i+1} y_i)\right|$$

各辺ベクトルの外積の総和の絶対値。整数座標なら誤差ゼロ。計算量 $O(N)$。

Step 2: 辺上の格子点数

線分 $(x_1, y_1) \to (x_2, y_2)$ 上の格子点数（両端含む）= $\gcd(|\Delta x|, |\Delta y|) + 1$。多角形全体では各辺の $\gcd$ を足す（隣接頂点を一度だけカウント）。

証明: $g = \gcd(dx, dy)$ とすると、方向ベクトル $(dx/g, dy/g)$ が最小ステップ。途中の格子点は $g-1$ 個（両端除く）。

Step 3: Pick の定理

$$A = I + \frac{B}{2} - 1 \implies I = \frac{2A - B + 2}{2}$$

$2A$ と $B$ はともに整数なので、$I$ が整数になることが保証される。

よくあるミス

次のステップ

• 発展: 3D 多面体の体積と格子点数（Ehrhart 多項式）
• 発展: 格子点多角形のラティス・バンドル
• 発展: 非格子点多角形の面積最小化問題

自己評価