Решение задачи 8.
Отсортируем концевые точки отрезков в порядке неубывания. Если несколько концевых точек отрезков имеют одинаковую координату, то сначала выпишем те из них, которые являются начальными точками отрезков, а за ними - конечные точки. Для такой сортировки необходимо для каждой точки сохранить информацию, является ли она правым или левым концом отрезка.
Рассмотрим одну из возможных реализаций:
Заведем массив A[1..2,1..2*N]; сначала в ячейки A[1,2i-1] и A[1,2i] заносим координаты начала и конца i-го отрезка, а в ячейки A[2,2i-1] и A[2,2i] - числа +i и -i -- признаки того, что соответствующие координаты являются началом и концом отрезка i. Сортируем столбцы массива A по неубыванию элементов первой строки, и если при этом несколько элементов первой строки равны (то есть соответствующие точки имеют одинаковые координаты), то сначала выписываем начальные точки отрезков (A[2,i]>0), а затем - конечные (A[2,2i-1]<0).
Заведем еще массив Pr[1..N], в котором будет храниться информация об отрезках, содержащих точку A[1,i]. После окончания работы алгоритма Pr[j]=1, если отрезок j содержит точку A[1,i], и Pr[j]=0 иначе. Сначала массив Pr нулевой.
Пусть в переменной C хранится количество отрезков, пересекающихся в точке A[1,i]. Сначала C=0.
Делаем проверку, размещается ли точка X левее A[1,1] или правее A[1,2*N]. Если да, то выводим сообщение о принадлежности точки бесконечному интервалу, если же нет, то будем просматривать массив A слева направо в порядке неубывания элементов.
Пока выполняется следующее условие:
массив A не закончился и
(или текущая точка A[1,i] < X
или текущая начальная точка отрезка A[1,i] = X)
повторять
Если A[1,i] - начальная точка отрезка,
то
увеличить C на 1 (начался еще один отрезок с номером A[2,i]), и присвоить Pr[A[2,i]] значение 1.
Если A[1,i] - конечная точка отрезка,
то
уменьшить C на 1 (отрезок с номером -A[2,i] закончился), и присвоить Pr[-A[2,i]] значение 0..
конец_пока.
Когда мы выйдем из цикла, то проверим:
Если С=0, то X лежит на межотрезочном интервале (A[1,i-1], A[1,i]), иначе X пpинадлежит C отpезкам. Номера отрезков есть индексы единичных элементов массива Pr.
Набросок этого фрагмента программы:
i:=1;
пока (i<=2*N) и
((A[1,i]<X) или
(A[1,i]=X) и (A[2,i]>0))
повторять
если A[2,i]>0
то C:=C+1;
Pr[A[2,i]:=1
конец_то
иначе C:=C-1;
Pr[-A[2,i]:=0
конец_иначе
i:=i+1;
конец_пока
если С=0,
то X лежит на межотрезочном интервале (A[1,i-1],A[1,i]),
иначе X пpинадлежит C отpезкам. Напечатаем номера этих отрезков:
для i:=1 до N повторять
если Pr[i]=1
то печатать i
|
