Отрезок однозначно определяется своими двумя конечными точками.
Рассматривая два отрезка на геометрической плоскости, возможны три варианта:
у отрезков нет общих точек, есть одна общая точка или бесконечное множество общих точек.

Более того, если у двух отрезков одна общая точка, то возможно, что эта общая точка является одним из концов либо одного отрезка, либо обоих. Если общая точка двух отрезков не является конечной точкой ни одного из них, то такая точка лежит на обоих отрезках.
Будем называть общую точку T двух отрезков L₁ и L₂ истинной точкой пересечения отрезков L₁ и L₂, если T является единственной общей точкой отрезков L₁ и L₂, и, одновременно, Т лежит на обоих отрезках (не являясь концом ни одного из них).

Рассмотрим три отрезка L₁, L₂, и L₃:

L₁: от (27, 44) до (12, 32)
L₂: от (46, 53) до (17, 62)
L₃: от (46, 70) до (22, 40)

Нетрудно убедиться в том, что у отрезков L₂ и L₃ есть истинная точка пересечения. Отметим, что, т.к. одна из конечных точек L₃: (22,40) лежит на отрезке L₁, она не является истинной точкой пересечения. У отрезков L₁ и L₂ нет общих точек. Таким образом, у этих трех отрезков есть одна истинная точка пересечения.

Теперь, повторим то же самое для 5000 отрезков. Для этого, сгенерируем 20000 псевдослучайных чисел, воспользовавашись так называемым алгоритмом Blum-Blum-Shub:

s₀ = 290797

s_n+1 = s_n×s_n (modulo 50515093)

t_n = s_n (modulo 500)

Для построения каждого отрезка воспользуемся четырьмя последовательными числами t_n. Это значит, что первый отрезок определяется следующими координатами:

от (t₁, t₂) до (t₃, t₄)

Первые четыре числа, сгенерированные с помощью этого алгоритма, будут равны 27, 144, 12 и 232. Таким образом, первый отрезок будет задаваться точками (27,144) и (12,232).

Сколько различных истинных точек пересечения можно найти у 5000 отрезков?