[中譯] ProjectEuler 465 Polar polygons

作者: tml (流刑人形)   2014-04-17 04:55:02
465. Polar polygons
http://projecteuler.net/problem=465
一個多邊形的核定義為在多邊形內部能看見所有邊界的點的集合。
我們定義極多邊形為包含原點在核的內部(通過核邊界者不算)的多邊形。
在這個題目中,多邊形的內角可以是平角,但是不能自交,且面積不得為0。
作為例子,下圖中只有最左邊的可以稱為極多邊形。(第二、三、四張圖中,原點不在
核的內部,而第五張圖的多邊形甚至完全沒有核。)
http://projecteuler.net/project/images/p465_polygons.png
注意到第一張圖的多邊形其實有一個平角。
令P(n)為所有極多邊形中,其坐標(x,y)的絕對值均不大於n的個數。
注意到即使兩多邊形包含的面完全相同,只要有一條邊不同即視為相異。
例如,由頂點[(0,0),(0,3),(1,1),(3,0)]圍出的多邊形和由頂點
[(0,0),(0,3),(1,1),(3,0),(1,0)]圍出的多邊形視為相異。
例如,P(1) = 131、P(2) = 1648531、P(3) = 1099461296175以及
P(343) mod 1000000007 = 937293740。
請求出P(7^13) mod 1000000007。

Links booklink

Contact Us: admin [ a t ] ucptt.com