Вход


Главная страница >> Учебный процесс >> Задачник >> Олимпиадные задачи (с решениями) >> Поиск >> Номер 8

[Назад]    [Содержание ]    [Вперед]

  


Номер 8


  Условие: Номер 8


Задача 8. На пpямой своими концами заданы N отpезков и точка X. Опpеделить, пpинадлежит ли точка межотpезочному интеpвалу. Если да, то указать концевые точки этого интервала. Если нет, то найти, а. Какому количеству отpезков пpинадлежит точка. б. Каким именно отрезкам принадлежит точка.

  Решение задачи: Номер 8


Решение задачи 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

Назад



[Назад]    [Содержание ]    [Вперед]

  


  
За содержание страницы отвечает Гончарова М.Н.
©
Кафедра СПиКБ, 2002-2017