Б. Каким именно отрезкам принадлежит точка

Отсортируем концевые точки отрезков в порядке неубывания. Если несколько концевых точек отрезков имеют одинаковую координату, то сначала выпишем те из них, которые являются начальными точками отрезков, а за ними - конечные точки. Для такой сортировки необходимо для каждой точки сохранить информацию, является ли она правым или левым концом отрезка.

Рассмотрим одну из возможных реализаций:

Заведем массив 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

Задача №11

Задана матрица натуральных чисел A(n,m). За каждый проход через клетку (i,j) взымается штраф A(i,j). Необходимо минимизировать штраф и