Как, используя алгоритм быстрой сортировки, определить лежит точка в массиве отрезков или нет?
Объединить вместе в один массив точки начал (с доп.полем "+1") и концов (с доп.полем "-1") отрезков и отсортировать его по координате :[11,+1],[17,+1],[21,-1],[32,+1],[37,-1],[42,-1]
А затем один раз пройтись по нему накапливая сумму доп.поля.
Можно решить и за линейное время (после сортировок):
1) берём массив концов отрезков (xi,1) и (yi,-1), сортируем (не забывая, что при одинаковых первых числах сначала идут все начала отрезков, а потом все концы: так для отрезков [1,2] и [2,3] получим массив (1,1),(2,1),(2,-1),(3,-1))
2) берём массив длиной n (число точек), заполняем его числами от 1 до n (если пишем на C-подобных языках - то от 0 до n-1). Cортируем массив, используя условие less(a,b)=(P[a] < P[b]), где P - массив точек. Получим индексы точек, отсортированные по возрастанию координат соответствующих точек.
3) Идём по обоим массивам, сравниваем координаты. Когда проходим точку в массиве концов, то прибавляем к счётчику второй элемент. Когда достигаем координаты очередной точки из P - записываем в массив результатов значение счётчика. Не забываем, что точка P[a]=x обрабатывается после всех точек (x,1) но до всех точек (x,-1) из массива концов.
4) Выводим массив результатов.