Énoncé:
Un segment est défini de manière unique par ses deux extrémités.
En considérant deux segments de droite en géométrie plane, il y a trois possibilités:
les segments ont zéro point, un point, ou une infinité de points communs.
De plus, lorsque deux segments ont exactement un point commun, il se peut que ce point commun soit un point d'extrémité de l'un des segments ou des deux. Si un point commun de deux segments n'est pas un point d'extrémité de l'un ou l'autre des segments, il est un point intérieur des deux segments.
Nous appellerons un point commun $T$ de deux segments $L_1$ et $L_2$ un vrai point d'intersection de $L_1$ et $L_2$ si $T$ est le seul point commun de $L_1$ et $L_2$ et si $T$ est un point intérieur des deux segments.
Considérons les trois segments $L_1$, $L_2$ et $L_3$:
$$L_1 : (27, 44) \ \text{à} \ (12, 32)$$
$$L_2 : (46, 53) \ \text{à} \ (17, 62)$$
$$L_3 : (46, 70) \ \text{à} \ (22, 40)$$
On peut vérifier que les segments de droite $L_2$ et $L_3$ ont un vrai point d'intersection. Nous notons que, comme l'un des points d'extrémité de $L_3 : (22, 40)$ se trouve sur $L_1$, il n'est pas considéré comme un véritable point d'intersection. $L_1$ et $L_2$ n'ont pas de point commun. Ainsi, parmi les trois segments de droite, nous trouvons un seul vrai point d'intersection.
Faisons maintenant la même chose pour $5000$ segments de ligne. À cette fin, nous générons $20000$ nombres à l'aide du générateur de nombres pseudo-aléatoires dit "Blum Blum Shub".
$$s_0 = 290797$$
$$s_{n+1} = s_n \times s_n \mod 50515093$$
$$t_n = s_n \mod 500$$
Pour créer chaque segment de ligne, nous utilisons quatre nombres consécutifs $t_n$. C'est-à-dire que le premier segment de ligne est donné par :
$(t_1, t_2)$ à $(t_3, t_4)$
Les quatre premiers nombres calculés selon le générateur ci-dessus devraient être : $27$, $144$, $12$ et $232$. Le premier segment serait donc de $(27,144)$ à $(12,232)$.
Combien de vrais points d'intersection distincts sont trouvés parmi les $5000$ segments de ligne ?
Lien du problème originel