65 lines
2.3 KiB
Markdown
65 lines
2.3 KiB
Markdown
---
|
||
id: 5900f4111000cf542c50ff24
|
||
title: 'Problema 165: intersezioni'
|
||
challengeType: 5
|
||
forumTopicId: 301799
|
||
dashedName: problem-165-intersections
|
||
---
|
||
|
||
# --description--
|
||
|
||
Un segmento è definito unicamente dai punti terminali. Considerando due segmenti in un piano geometrico ci sono tre possibilità: i due segmenti hanno zero punti, un punto, o infiniti punti in comune.
|
||
|
||
In più quando i due segmenti hanno esattamente un punto in comune potrebbe essere che questo sia un terminale di uno o entrambi i segmenti. Se un punto in comune dei due segmenti non è un punto terminale di nessuno dei due allora è un punto interno di entrambi i segnmenti.
|
||
|
||
Sia $T$, un punto in comune di due segmenti $L_1$ e $L_2$, un vero punto d'intersezione se è il solo punto in comune di $L_1$ e $L_2$ ed è un punto interno di entrambi i segmenti.
|
||
|
||
Considera i tre segmenti $L_1$, $L_2$, e $L_3$:
|
||
|
||
$$\begin{align} & L_1: (27, 44) \\;\text{to}\\; (12, 32) \\\\
|
||
& L_2: (46, 53) \\;\text{to}\\; (17, 62) \\\\ & L_3: (46, 70) \\;\text{to}\\; (22, 40) \\\\
|
||
\end{align}$$
|
||
|
||
Si può verificare che i segmenti $L_2$ e $L_3$ hanno un vero punto di intersezione. Notiamo che essendo uno dei terminali di $L_3$: (22, 40) su $L_1$ questo non è un vero punto d'intersezione. $L_1$ e $L_2$ non hanno un punto in comune. Quindi tra i tre segmenti troviamo un vero punto di intersezione.
|
||
|
||
Adesso facciamo lo stesso per 5000 segmenti. A questo fine, generiamo 20000 numeri casuali usando il generatore pseudo-casuale di numeri chiamato "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}$$
|
||
|
||
Per creare ogni segmento, usiamo quattro numeri consecutivi $t_n$. Quindi, il primo segmento è dato da:
|
||
|
||
da ($_t$1, $t_2$) a ($t_3$, $t_4$)
|
||
|
||
I primi quattro numeri calcolati con il precedente generatore dovrebbero essere: 27, 144, 12 e 232. Quindi il primo segnmento è da (27, 144) a (12, 232).
|
||
|
||
Quante intersezioni vere sono trovate tra i 5000 segmenti?
|
||
|
||
# --hints--
|
||
|
||
`distinctIntersections()` should return `2868868`.
|
||
|
||
```js
|
||
assert.strictEqual(distinctIntersections(), 2868868);
|
||
```
|
||
|
||
# --seed--
|
||
|
||
## --seed-contents--
|
||
|
||
```js
|
||
function distinctIntersections() {
|
||
|
||
return true;
|
||
}
|
||
|
||
distinctIntersections();
|
||
```
|
||
|
||
# --solutions--
|
||
|
||
```js
|
||
// solution required
|
||
```
|