Files

55 lines
2.6 KiB
Markdown
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

---
id: 5900f53d1000cf542c510050
title: 'Завдання 465: Полярні багатокутники'
challengeType: 5
forumTopicId: 302140
dashedName: problem-465-polar-polygons
---
# --description--
Ядро багатокутника визначається сукупністю точок, з яких видно сторони багатокутника. Ми визначаємо полярний багатокутник як багатокутник, джерело якого міститься суворо всередині ядра.
У такому випадку багатокутник може мати послідовні колінеарні вершини. Однак він не може перетинатися та мати нульову площу.
Наприклад, тільки перший з наведених багатокутників є полярним (ядра другого, третього та четвертого не вміщують джерело повністю, а п'ятий взагалі не має ядра):
<img class="img-responsive center-block" alt="п'ять прикладів багатокутників" src="https://cdn.freecodecamp.org/curriculum/project-euler/polar-polygons.png" style="background-color: white; padding: 10px;" />
Зверніть увагу, що перший багатокутник має три послідовні колінеарні вершини.
Нехай $P(n)$ буде кількістю полярних багатокутників, вершини яких $(x, y)$ мають цілі координати, абсолютні значення яких не більші за $n$.
Зверніть увагу, що багатокутники вважаються різними, якщо вони мають різний набір сторін, навіть якщо вони оточують одну й ту ж саму область. Наприклад, багатокутник з вершинами [(0,0), (0,3), (1,1), (3,0)] відрізняється від багатокутника, що має вершини [(0,0), (0,0), (1,1), (3,0), (3,0), (1,0)].
Наприклад, $P(1) = 131$, $P(2) = 1\\,648\\,531$, $P(= 1\\,099\\,461\\,296\\,175$ та $P(343)\bmod 1\\,000\\,007 = 937\\,293\\,740$.
Знайдіть $P(7^{13})\bmod 1\\,000\\,007$.
# --hints--
`polarPolygons()` повинен повертатися як `585965659`.
```js
assert.strictEqual(polarPolygons(), 585965659);
```
# --seed--
## --seed-contents--
```js
function polarPolygons() {
return true;
}
polarPolygons();
```
# --solutions--
```js
// solution required
```