Как, используя алгоритм быстрой сортировки, определить лежит точка в массиве отрезков или нет?

Доброго всем дня.

Прохожу курс по алгоритмам и одно из заданий таково:
Даны отрезки вида [x, y], где x - координата начала отрезка, а у, соответственно, координата конца. Также дан массив точек [x1, x2, x3, ... , xn]. Необходимо определить в каком количестве отрезков содержится каждая точка. Задание находится в теме "Быстрая сортировка" и очевидно, что использовать нужно её, но я не понимаю, с чего нужно начинать.
Наивный алгоритм за O(n^2) ясен, для каждой точки пробегаемся по всем возможным отрезкам.
Далее приведу свои дальнейшие рассуждения по прикручиванию быстрой сортировки:
1. Сортировать массив точек не имеет смысла, так как выдавать результат по каждой точке необходимо в порядке появления её в потоке ввода.
2. Объединять все массивы отрезков в один также не имеет смысла, потому что тогда мы не сможем контролировать начало и конец отрезка, так как все смешается в упорядоченную кашу.
3. Создать два массива для начал и концов отрезков ( 1: [x1, x2, x3, ... , xn], 2: [y1, y2, y3, ... , yn]
Отсортировать их с помощью "быстрой" сортировки (используя тройное разделение для ускорения сортировки повторяющихся элементов) и...
Что делать дальше мне не совсем понятно. Просто последовательно проходить по упорядоченным массивам [x] и [y] для каждой точки, тем самым получив число отрезков, в которые точка входит или как?

Буду признателен за любую помощь.
  • Вопрос задан
  • 3072 просмотра
Решения вопроса 1
Mrrl
@Mrrl
Заводчик кардиганов
Можно решить и за линейное время (после сортировок):
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) Выводим массив результатов.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
Объединить вместе в один массив точки начал (с доп.полем "+1") и концов (с доп.полем "-1") отрезков и отсортировать его по координате :
[11,+1],[17,+1],[21,-1],[32,+1],[37,-1],[42,-1]
А затем один раз пройтись по нему накапливая сумму доп.поля.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы