例题一:简单四边形
题目:一个格点四边形的顶点坐标分别为 (0,0), (4,0), (4,3), (0,3)。求其面积。
解法:
1. 内部格点数 i:x∈{1,2,3}, y∈{1,2},共 3×2=6 个。
2. 边界格点数 b:
- (0,0)到(4,0):5个
- (4,0)到(4,3):4个
- (4,3)到(0,3):5个
- (0,3)到(0,0):4个
- 顶点重复计算,需减去4个重复顶点,或直接数:底边5+右边3(不含顶点)+顶边3(不含顶点)+左边2(不含顶点)+4个顶点 = 10个。
3. 公式:S = 6 + 10/2 - 1 = 6 + 5 - 1 = 10。
传统方法:长4宽3的矩形,面积 4×3=12?不对,这是矩形。等等,坐标是(0,0),(4,0),(4,3),(0,3),这是矩形。面积确实是12。让我重新数一下。
修正:边界点:
底边:(0,0),(1,0),(2,0),(3,0),(4,0) -> 5个
右边:(4,1),(4,2) -> 2个 (不含顶点)
顶边:(3,3),(2,3),(1,3) -> 3个 (不含顶点)
左边:(0,2),(0,1) -> 2个 (不含顶点)
顶点:4个
总边界点 b = 5+2+3+2+4 = 16? 不对。
让我们用GCD公式:b = gcd(4,0) + gcd(0,3) + gcd(4,3) + gcd(0,3) ? 不对,是各边gcd之和。
边1: (0,0)-(4,0), dx=4, dy=0, gcd=4.
边2: (4,0)-(4,3), dx=0, dy=3, gcd=3.
边3: (4,3)-(0,3), dx=4, dy=0, gcd=4.
边4: (0,3)-(0,0), dx=0, dy=3, gcd=3.
b = 4+3+4+3 = 14.
内部点 i: x=1,2,3; y=1,2. 32=6.
S = 6 + 14/2 - 1 = 6 + 7 - 1 = 12. 正确。
结论:面积为 12。