題意: 給定一整數點的多邊形，求與此多邊形的形狀相同的最小多邊形及其M倍以內的多邊形內部所包含的整數點點數總和。
解法: 須先刪除共線的點，然後將多邊形的一頂點平移至原點，接著求出所有邊的x變量、y變量的最大公因數D，接著將所有座標除以D後即得到最小相似多邊形，接著可以皮克定理(Pick's Theorem) A = i + B/2 - 1 ，A為多邊形的面積，i為多邊行內部整數點點數，B為多邊形邊上點數，可應用此定理推出答案之公式，ans = S1*(m*(m+1)*(2m+1)/6) - (B/2)*(m*(m+1)/2) + m。
TAG: Computational Geometry
注意: 這題的測資非常的坑人，答案會趨近於2^64-1，所以最後算出來的答案非常容易爆炸，需要配合unsigned long long及long long使用。
沒有留言:
張貼留言
任何意見都樂意傾聽