@brainiac26

Как найти решение для задачи?

Каким алгоритмом решить задачу?
Предположим, мы хотим создать универсальную программную камеру, объединив множество негибких аппаратных камер. Каждая аппаратная камера хорошо работает для определенного диапазона расстояний до объекта и для определенного диапазона уровней освещенности. Программная камера будет измерять уровень освещенности и расстояние до объекта для каждого кадра и выбирать подходящую аппаратную камеру для его съемки. Напишите функцию, которая принимает желаемые характеристики программной камеры (диапазон расстояний до объекта и диапазон уровней освещенности, которые она должна поддерживать), а также список аппаратных камер с их соответствующими характеристиками и проверяет, будет ли этого набора аппаратных камер достаточно.
  • Вопрос задан
  • 170 просмотров
Пригласить эксперта
Ответы на вопрос 3
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Rsa97 правильно написал про геометрический смысл. Но есть более быстрое решение за O(n log n), использующее метод заметающей прямой.

Пересеките все прямоугольники с тем, который надо покрыть, отрезав от них торчащую наружу часть.

Если числа в задаче большие или нецелые, то сначала через бинпоиск или хешмап замените все координаты по X и по Y на их порядковый номер в отсортированном массиве (отдельно по каждой оси). Эта операция называется "сжатие координат". Теперь у вас все координаты целые числа от 0 до 2*n.

Потом примените алгоритм "заметающей прямой". Представьте, что вертикальная линия двигается слева-направо и "заметает" картинку. Вам надо отслеживать, какие прямоугольники ее пересекают в каждый момент времени и проверить, что вся прямая покрыта в каждый момент.

Для этого каждый прямоугольник (X1, Y1, X2, Y2) создаст 2 события "открылся отрезок с Y1 до Y2 во время X1" и "закрылся отрезок с Y1 до Y2 во время X2". Эти все события вы сортируете по X и в таком порядке обрабатываете.

Для отслеживания состояния прямой используйте дерево отрезков на минимум с отложенной суммой. Эта структура данных потребует массив на примерно 4n элементов для дерева с 2n листами. Каждая вершина будет хранить минимум на соответсвующем ей отрезке. При открытии прямоугольника вы должны добавить +1 на его отрезок. При закрытии - вычесть 1. Сначала открывайте прямоугольники, если время у событий одинаковое. Учитывайте это при сортировке. Так касающиеся по вертикали прямоугольники не создадут пустых мест.
Если после обработки какого-либо события вы получили минимум в дереве отрезков 0 и следующее событие имеет большую координату по X - то какая-то часть оказалась не покрыта. Еще есть случай, если первое событие не X1=левая граница покрываемого прямоугольника, или последнее событие - не X2=правая граница всего прямоугольника. Тут тоже покрытия нет.

Еще, аккуратно с целыми числами, чтобы если у вас 2 прямоугольника касаются горизонтальными сторонами - там пустое место не подсчиталось. Например, каждый лист дерева отвечает за единичный отрезок координат. Тогда изменяйте в дереве всегда отрезок от Y1 до Y2-1 для события с координатам Y1..Y2.
Ответ написан
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Геометрически здесь задача проверки, что заданный в координатах X(distance) - Y(light) прямоугольник полностью покрывается набором других прямоугольников.
Как вариант, формируем общий список левых и правых границ всех покрывающих прямоугольников по X, сортируем его, слева и справа ограничиваем целевым прямоугольником, затем для каждого интервала проверяем, что он полностью покрывается по Y.
Например:
Целевой прямоугольник (1, 1)-(6, 6)
Покрывающие прямоугольники: (0, 0)-(3, 4), (2, 1)-(7, 5), (0, 3)-(6, 7)
Составляем список границ по X: 0, 3, 2, 7, 0, 6
Удаляем дубли, сортируем и ограничиваем по [1, 6]: 1, 2, 3, 6
Для каждого интервала составляем список интервалов по Y и объединяем интервалы:
[1, 2]: [0, 4] + [3, 7] = [0, 7], что перекрывает целевой [1, 6]
[2, 3]: [0, 4] + [1, 5] + [3, 7] = [0, 7], что перекрывает целевой [1, 6]
[3, 6]: [1, 5] + [3, 7] = [1, 7], что перекрывает целевой [1, 6]
На всех интервалах полное покрытие, значит целевой прямоугольник покрывается полностью.
Сложность, правда, высокая - n2.
Ответ написан
Комментировать
mayton2019
@mayton2019
Bigdata Engineer
Мы ищем функцию select_camera следующего вида. (На неком подобии Python/Scala)

case class Range(begin:Double,end:Double)

case class CameraProps(distance_range : Range, luminosity_range : Range) 

def select_camera(distance : Double, luminosity : Double, cams : List[CameraProps]) : List[Int] = {
  ....
}


По смыслу мы можем найти не одну а много камер, удовлетворяющих условию. Тоесть результат
это - список камер.

По реализации - это похоже на поиск точки, которая попадает в прямоугольники.

Быстрые алгоритмы и структура это QuadTree-s, R-Trees (Antonin Guttman).
И те и другие - подходят. Они по сути - вспомогательные структуры для ускорения поиска камер.

При условии что точка будет двигаться а камеры стоят стационарно а искать надо много.

Если двигаются и камеры и точки - то тогда надо искать другие структуры данных.
Ответ написан
Комментировать
Ваш ответ на вопрос

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

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