EZ
мб там какой-то хитрый прямоугольник
Size: a a a
2021 June 07
EZ
интуитивно нет конечно
2021 June 08
TS
контент, который мы заслужили
2021 June 09
T
а существует ли какой-нибудь алгоритм, позволяющий на лету объединять отрезки?
T
я посмотрел в сторону дерева отрезков, но оно, видимо, только позволяет их хранить как отдельные сущности
PO
В смысле? Даны n отрезков от a до b и надо их объединять? Просто берешь и объединяешь
T
они даны в случайном порядке
PO
Ну отсорть
T
по сути это как сделать побитовый OR очень большой битовой карты
PO
Засунь в сет
PO
Померджи
FO
ага... отсортировать (1) по началу в возрастающем порядке, и (2) по концу в убывающем порядке (память будем экономить)
затем просто проверять границы
затем просто проверять границы
T
ну наверное хватит отсортировать даже просто по началу
FO
ну.. если ещё и по концу сравнивать, то можно прям в процессе сортировки будет часть элементов выкидывать
DP
а что если так:
берем пустое дерево отрезков
берем случайный отрезок из данных нам
делаем поиск в дереве отрезков на наличие отрезков перевекающихся с тем что мы взяли
если пересечений нет - добавляем новый отрезок в дерево. если пересечения есть - мержим отрезок и тот с которыми он пересекается
что-то около O(N*logN), работает на лету, не нужно сортировать входящие данные
берем пустое дерево отрезков
берем случайный отрезок из данных нам
делаем поиск в дереве отрезков на наличие отрезков перевекающихся с тем что мы взяли
если пересечений нет - добавляем новый отрезок в дерево. если пересечения есть - мержим отрезок и тот с которыми он пересекается
что-то около O(N*logN), работает на лету, не нужно сортировать входящие данные
DP
детально:
если пересечение - удаляем "внутренние" концы обоих отрезков и делаем более длинный отрезок.
если один отрезок включает другой - удаляем более мелкий отрезок.
если пересечение - удаляем "внутренние" концы обоих отрезков и делаем более длинный отрезок.
если один отрезок включает другой - удаляем более мелкий отрезок.
2021 June 10
GK
Всё бы ничего, но добавляемый отрезок может включать больше двух уже существующих.
GK
(—[1]——[-2-]——[3]—)
GK
Хотя я не прав: достаточно найти самый левый и самый правый отрезок с пересечением, а потом выкинуть внутренние поддеревья.