3.4 KiB
id, title, challengeType, forumTopicId, dashedName
| id | title | challengeType | forumTopicId | dashedName |
|---|---|---|---|---|
| 5900f4111000cf542c50ff24 | Задача 165: Перетини | 5 | 301799 | 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{to}\; (12, 32) \\ & L_2: (46, 53) \;\tтекст{to}\; (17, 62) \\ & L_3: (46, 70) \;\tтекст{to}\; (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.
assert.strictEqual(distinctIntersections(), 2868868);
--seed--
--seed-contents--
function distinctIntersections() {
return true;
}
distinctIntersections();
--solutions--
// solution required