Как решить данную задачу за O(log(n)*n)?

Question

[Даниил Сорокин]

Добрый день. Столкнулся с трудностями в решении задачи за время O(log(n)*n). Суть задачи: есть координатная плоскость на которой, по оси Х распологаются круги с определенными радиусами. Дан массив А в котором индекс - обозначает центр круга на оси Х, а значение - радиус этого круга. Нужно найти кол-во пересечений. Вот ссылка на задачу https://codility.com/programmers/task/number_of_di... Не прошу полного решения, подтолкните куда копать

Answer 1

[mamkaololosha]

Complexity:
expected worst-case time complexity is O(N*log(N));
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Судя по описанию это не O(n), не greedy и не single pass. Возможно динамическое программирование + сортировка.

Answer 2

[Александра Воронцова]

Эту задачу можно решить методом сканирующей прямой. Добавьте для каждого круга на окружность 2 точки: точку первого пересечения с прямой и точку второго пересечения с прямой. Точка это на самом деле структура, которая знает свою координату, к какой окружности она относится и является ли она точкой с меньшей или с большей координатой х для этой прямой)
За N log N сортируем окружности по значениям X.
Далее просматриваем все окружности. На каждом шаге нам надо решить как обновить число пересечений. Далее порисуйте варианты на листочке и найдите решение :)

Answer 3

[Mercury13]

Создадим массив на 2N событий. Событие — эти тип («начало»/«конец»), № круга и координата. Каждый круг создаёт два события: начало на i−R и конец на i+R.
Массив сортируем по X, с таким уточнением, если X равны.
• Если касание считать пересечением, начало < конец (т.е. для точки X идут начала, затем концы). В такой ситуации нам не важны номера кругов.
• Если нет — сначала номера кругов (aka x-координаты центров) по возрастанию, затем начало < конец.
Заводим счётчик кругов. Проходимся по массиву.
• Если видим начало — к результату +счётчик, к счётчику +1.
• Если видим конец — к счётчику −1.

В нашем примере:
Счётчик 0, результат 0
Начало №1 на x=−4: результат 0, счётчик 1
Начало №0 на x=−1: результат 1, счётчик 2
Начало №2 на x=0: результат 3, счётчик 3
Начало №4 на x=0: результат 6, счётчик 4
Конец №0 на x=1: счётчик 3
Начало №3 на x=2: результат 9, счётчик 4
Затем аж два конца на x=4, счётчик опустился до 2
Начало №5 на x=5: результат 11, счётчик 3
Конец №5 на x=5: счётчик 2
И ещё два конца сбрасывают счётчик до 0.

UPD. Уточнил для случая, если касание — не пересечение.