Lattice

Lattice

UVa 11768

Pick's Theorem

計算簡單多邊形內部格點數目,多邊形的頂點剛好都在格點上

利用Pick's Theorem可以迅速求出簡單多邊形內部會有多少像素,限制是簡單多邊形的頂點必須不偏不倚位於像素上。

簡單多邊形面積 = 簡單多邊形圍住的像素數目 + 簡單多邊形上的像素數目 / 2 - 1

簡單多邊形其中一條邊上面的像素數目,可以利用邊的起點座標與終點座標,以X軸差與Y軸差的最大公因數求得。

UVa 10088

計算簡單多邊形內部格點數目,多邊形的頂點在任意位置

【待補文字】

Farey Sequence

http://www.matrix67.com/blog/archives/2199

UVa 10408 10214

Integer Relation(Under Construction)

http://oldweb.cecm.sfu.ca/projects/IntegerRelations/fpsac97/

lattice basis reduction

http://cseweb.ucsd.edu/classes/wi12/cse206A-a/
http://cseweb.ucsd.edu/classes/wi10/cse206a/

Integer Relation: Lenstra-Lenstra-Lovasz Algorithm(Under Construction)

Integer Relation: HJLS Algorithm(Under Construction)

Integer Linear Programming: Barvinok's Algorithm(Under Construction)

計算半平面交內部格點數目

丟番圖改成不等式。