Задача 165: Пересечения
Сегмент однозначно определяется двумя его конечными точками. Рассматривая два отрезка в плоской геометрии, существует три возможности: сегменты имеют нулевые точки, одну точку или бесконечно много общих точек. Более того, когда два сегмента имеют ровно одну общую точку, может быть, что эта общая точка является конечной точкой либо одного из сегментов, либо обоих. Если общая точка двух сегментов не является конечной точкой любого из сегментов, она является внутренней точкой обоих сегментов. Будем называть общую точку T двух сегментов L1 и L2 истинной точкой пересечения L1 и L2, если T - единственная общая точка L1 и L2, а T - внутренняя точка обоих сегментов.
Рассмотрим три сегмента L1, L2 и L3: L1: (27, 44) - (12, 32) L2: (46, 53) - (17, 62) L3: (46, 70) - (22, 40) Можно проверить, что сегменты линии L2 и L3 имеют истинную точку пересечения. Заметим, что, поскольку одна из конечных точек L3: (22,40) лежит на L1, это не считается истинной точкой пересечения. L1 и L2 не имеют общей точки. Таким образом, среди трех сегментов линии мы находим одну истинную точку пересечения. Теперь сделаем то же самое для 5000 сегментов линии. С этой целью мы генерируем 20000 номеров, используя так называемый генератор псевдослучайных чисел Blum Blum Shub. s0 = 290797 sn + 1 = sn × sn (по модулю 50515093) tn = sn (по модулю 500). Чтобы создать каждый сегмент линии, мы используем четыре последовательных числа tn. То есть первый сегмент линии задается следующим образом: (t1, t2) - (t3, t4) Первые четыре числа, вычисленные в соответствии с указанным выше генератором, должны быть: 27, 144, 12 и 232. Таким образом, первый сегмент будет ( 27, 144) - (12 232). Сколько четких точек пересечения найдено среди 5000 сегментов линии?