這題要用到的數學定理還蠻多的。

(1) Pick定理:

頂點座標均是正方格點,有以下定理。

面積A = 內部點數目i + 邊上點數目b/2 - 1。

(2)

以格子點為頂點的線段,覆蓋的點的個數為 GCD(dx,dy) ,其中,dxdy分別為線段橫向佔的點數和縱向佔的點數。

如果dx或dy為0,則覆蓋的點數為dy或dx。

(3)

任意一個多邊形的面積等於按順序求相鄰 兩個點與原點組成的向量的叉積之和/2 之絕對值。


有了以上3個定理,可以利用 (3) 求出題目要求之面積,利用 (2) 算出邊上的點數目,最後用 (2), (3) 的結果利用 (1) 算出內部的點數目,即為題目所求。

我的code

http://codepad.org/KIhYZsKK


文章標籤
創作者介紹
創作者 jghs1328 的頭像
jghs1328

jghs1328

jghs1328 發表在 痞客邦 留言(0) 人氣()