Files
gikf 397a9f0c3e fix(curriculum): clean-up Project Euler 462-480 (#43069)
* fix: clean-up Project Euler 462-480

* fix: missing image extension

* fix: corrections from review

Co-authored-by: Tom <20648924+moT01@users.noreply.github.com>

Co-authored-by: Tom <20648924+moT01@users.noreply.github.com>
2021-07-30 08:32:21 -07:00

1.8 KiB

id, title, challengeType, forumTopicId, dashedName
id title challengeType forumTopicId dashedName
5900f53d1000cf542c510050 Problem 465: Polar polygons 5 302140 problem-465-polar-polygons

--description--

The kernel of a polygon is defined by the set of points from which the entire polygon's boundary is visible. We define a polar polygon as a polygon for which the origin is strictly contained inside its kernel.

For this problem, a polygon can have collinear consecutive vertices. However, a polygon still cannot have self-intersection and cannot have zero area.

For example, only the first of the following is a polar polygon (the kernels of the second, third, and fourth do not strictly contain the origin, and the fifth does not have a kernel at all):

five example polygons

Notice that the first polygon has three consecutive collinear vertices.

Let P(n) be the number of polar polygons such that the vertices (x, y) have integer coordinates whose absolute values are not greater than n.

Note that polygons should be counted as different if they have different set of edges, even if they enclose the same area. For example, the polygon with vertices [(0,0), (0,3), (1,1), (3,0)] is distinct from the polygon with vertices [(0,0), (0,3), (1,1), (3,0), (1,0)].

For example, P(1) = 131, P(2) = 1\\,648\\,531, P(3) = 1\\,099\\,461\\,296\\,175 and P(343)\bmod 1\\,000\\,000\\,007 = 937\\,293\\,740.

Find P(7^{13})\bmod 1\\,000\\,000\\,007.

--hints--

polarPolygons() should return 585965659.

assert.strictEqual(polarPolygons(), 585965659);

--seed--

--seed-contents--

function polarPolygons() {

  return true;
}

polarPolygons();

--solutions--

// solution required