[中译] 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