---
id: 5900f4111000cf542c50ff24
title: 'Завдання 165: перетини'
challengeType: 1
forumTopicId: 301799
dashedName: problem-165-intersections
---

# --description--

Відрізок визначається лише двома кінцевими точками. Розглядаючи два відрізки у планіметрії є три варіанти: відрізки не мають спільних точок, мають одну спільну точку або мають нескінченно багато спільних точок.

Крім того, коли два відрізки мають лише одну спільну точку, це може бути той випадок, коли спільною точкою є кінцева точка або одного з відрізків, або обох. Якщо спільна точка двох відрізків не є кінцевою точкою будь-якого із відрізків, то це внутрішня точка обох відрізків.

Назвемо спільну точку $T$ двох відрізків $L_1$ й $L_2$ точкою перетину $L_1$ й $L_2$, якщо $T$ є єдиною спільною точкою $L_1$ й $L_2$, а $T$ є внутрішньою точкою обох відрізків.

Розглянемо три відрізки $L_1$, $L_2$ та $L_3$:

$$\begin{align}   & L_1: від (27, 44) \\;\text{до}\\; (12, 32) \\\\
  & L_2: від (46, 53) \\;\text{до}\\; (17, 62) \\\\   & L_3: від (46, 70) \\;\text{до}\\; (22, 40) \\\\
\end{align}$$

Можна довести, що відрізки $L_2$ та $L_3$ мають точку перетину. Зазначимо, що оскільки одна кінцева точка $L_3$ (22, 40) лежить на $L_1$, вона не являється точкою перетину. $L_1$ та $L_2$ не мають спільних точок. Тому серед трьох відрізків ми знайшли лише одну точку перетину.

Тепер зробимо те саме для 5000 відрізків. З цією метою ми згенеруємо 20000 чисел, використовуючи так званий генератор псевдовипадкових чисел «Blum Blum Shub».

$$\begin{align}   & s_0 = 290797 \\\\
  & s_{n + 1} = s_n × s_n (\text{modulo}\\; 50515093) \\\\   & t_n = s_n (\text{modulo}\\; 500) \\\\
\end{align}$$

Щоб створити кожен відрізок, ми використовуємо чотири послідовних числа $t_n$. Тобто перший відрізок задано цими координатами:

від ($_t$1, $t_2$) до ($t_3$, $t_4$)

Перші чотири числа вичислені згідно зі згаданим генератором: 27, 144, 12 та 232. Тобто перший відрізок задається точками (27, 144) та (12, 232).

Скільки окремих точок перетину буде знайдено серед 5000 відрізків?

# --hints--

`distinctIntersections()` має повернути `2868868`.

```js
assert.strictEqual(distinctIntersections(), 2868868);
```

# --seed--

## --seed-contents--

```js
function distinctIntersections() {

  return true;
}

distinctIntersections();
```

# --solutions--

```js
// solution required
```
