Нахождение координат наиболее подходящего прямоугольника

Question

Ввод: A, B, a, b - где A и B - моя ширина и высота сетки, а a, b - ширина и высота прямоугольника, в который я хочу вписаться. Тогда мне дано N - число прямоугольников, которые уже вписаны в сетку. В следующих N строках мне даны координаты противоположных диагональных вершин каждого прямоугольника, например, для первого прямоугольника, ввод будет (x0, y0) (x1, y1) и так далее. Эти прямоугольники могут перекрываться. И мне нужно найти координаты противоположных диагональных вершин исходного прямоугольника, чтобы он мог поместиться в сетке (нам нужно вывести максимальную высоту) Пример:

9 5 2 4
2
1 1 3 4
1 1 6 2

Вывод будет be: 6 0 8 5 Изображение ввода Не могли бы вы дать мне несколько советов? Кажется, что мне нужно использовать Dynami c программирования здесь

Answer 1

Если предположить, что все координаты являются целыми числами, то вы можете рассмотреть все возможные прямоугольники с шириной a и высотой >=b, вписанные в граничный прямоугольник с шириной A и высотой B - это легко увидеть, что их число O(AB^2). Вам нужно будет проверить пересечение каждого такого прямоугольника с вашими N предопределенными прямоугольниками. Существуют структуры данных, такие как Quadtree , которые позволят вам выполнить один тест пересечения за O(logN) раз.

В более общем случае вы можете использовать Plane Sweep подход, и это будет намного быстрее. Я кратко опишу это здесь.

Сначала вам нужно отсортировать все X -координаты, которые у вас есть, включая координаты граничного прямоугольника (вы называете это grid ). Каждый элемент этого отсортированного массива S должен хранить само значение X -координаты вместе с номером прямоугольника, которому он принадлежит, и флаг, отмечающий левую или правую сторону этого прямоугольника.

Теперь представьте «скользящий» прямоугольник T с шириной a и высотой B, расположенный в крайнем левом положении внутри граничного прямоугольника - его левая сторона будет иметь координату S[0].x. Вы можете найти все прямоугольники, пересекающиеся с прямоугольником T, смотрящим только на массив S - давайте назовем этот набор прямоугольников активным набором . Вам необходимо выяснить, есть ли у вас пустое пространство с высотой >=b на пересечении T с активным набором. Запомните максимальный прямоугольник с шириной a и максимальной высотой >=b (если он существует).

Смещайте скользящий прямоугольник T вправо, пока его левая сторона не достигнет координаты S[1].x. Опять же, вы можете использовать массив S, чтобы найти активный набор, пересекающийся с T, и выполнить тот же локальный анализ, как и раньше. Если вы можете найти пустое пространство внутри скользящего прямоугольника, сравните его с уже найденным и запомните лучший результат.

Продолжайте этот процесс, пока скользящий прямоугольник T не достигнет правой стороны граничного прямоугольника. Количество смен здесь O(N), и временная сложность этого алгоритма зависит от того, насколько эффективно вы можете найти пустое место на каждом шаге. Здесь возможно множество подходов - самый простой будет основан на сортировке Y -координат. Также вы можете представлять активный набор прямоугольников, используя некоторую структуру данных. Я оставляю эту часть тебе.