В этом задании вам дается два перекрывающихся прямоугольника, и вам нужно вычислить прямоугольники, созданные путем удаления одного из другого.
Например, если вы удалите красный прямоугольник из черного:
Вы получите один из следующих двух наборов прямоугольников:
Вам также нужно будет обработать следующее:
Чтобы быть более явным:
- Вы введете координаты двух прямоугольников A и B.
- Вам нужно вывести наименьшее количество непересекающихся прямоугольников, которые покрывают всю область A без B. Допускается любое возможное покрытие
- Прямоугольные координаты передаются как 4 целых числа. Вы можете передать их в две пары (представляющие две угловые точки) или в виде кортежа / списка из 4 целых чисел. Ваши входы и выходы должны быть согласованы.
- A и B не обязательно будут перекрываться или касаться друг друга, и каждый будет иметь площадь по меньшей мере 1
Тестовые случаи:
[(0 0) (5 5)] [(3 4) (8 7)] -> [(0 0) (5 4)] [(0 4) (3 5)] # or [(0 0) (3 5)] [(3 0) (5 4)]
[(2 4) (10 11)] [(5 5) (6 6)] -> [(2 4) (10 5)] [(2 5) (5 6)] [(6 5) (10 6)] [(2 6) (10 11)] #Other sets of 4 rectangles are possible
[(3 3) (8 8)] [(0 1) (10 8)] -> #No rectangles should be output
[(0 0) (5 5)] [(1 1) (10 2)] -> [(0 0) (1 5)] [(1 0) (2 1)] [(2 0) (5 5)] #Other sets of 3 rectangles are possible
[(1 5) (7 8)] [(0 0) (1 10)] -> [(1 5) (7 8)] #Only possible output
[(4 1) (10 9)] [(2 5) (20 7)] -> [(4 1) (10 5)] [(4 7) (10 9)] #Only possible output
[(1 1) (8 8)] [(0 6) (9 9)] -> [(1 1) (8 6)] #Only possible output
Это код-гольф , поэтому сделайте ваш код как можно короче!
code-golf
geometry
grid
set-partitions
Натан Меррилл
источник
источник
{(x1, y1), (x2, y2)}
имеет местоx1 < x2
иy1 < y2
?Ответы:
Python 2 ,
375360345343 байтаПопробуйте онлайн!
РЕДАКТИРОВАТЬ: -15 из предложений от @notjagan; еще -15 путем перекодирования массива прямоугольников решения в формат int36 и краткой таблицы поиска; еще -2, заменив продукт на p согласно @musicman.
Функция, которая принимает два прямоугольника, каждый из которых является кортежем ((слева, сверху), (справа, снизу)); возвращает список полученных прямоугольников.
Основная стратегия:
На приведенной выше диаграмме точки A и B - это верхний левый и нижний правый соответственно прямоугольник «Источник» (первый прямоугольник).
Мы находим расположение каждого из верхнего левого
(u,v)
и нижнего правого(x,y)
прямоугольника «Маска» в этой сетке.Если обе эти точки находятся в первом или последнем столбце; или первый или последний ряд; тогда нет перекрытия; и мы можем вернуть только исходный прямоугольник.
В противном случае осталось 16 случаев; Например, первый пример OP - это случай, который мы можем пометить
(1,1),(2,2)
. Каждый случай может быть сопоставлен с набором результирующих прямоугольников, углы которых всегда являются координатами с горизонтальными значениями в исходных прямоугольниках слева, справа или в прямоугольниках маски слева, справа; и аналогично для вертикальных значений, верха, низа или масок источника.Например, для данного
(1,1),(2,2)
случая прямоугольники будут((l,t),(T,r))
и((l,T),(R,b))
, гдеl,t,r,b
иL,T,R,B
- это левый, верхний, правый и нижний прямоугольники источника и маски соответственно.Таким образом, мы можем создать справочную таблицу, которая отображает координаты в набор всех таких возможных комбинаций (о чем и говорит этот
product(product(*zip(*)))
бит) в набор прямоугольников, которые должны быть предоставлены для каждого из случаев (которые после некоторой декомпрессии в гольфе) , это то, о чем остальная часть материала списка).источник
p=product
и заменивproduct(product
наp(p
JavaScript, 115 байт
перекрывающаяся версия:
Введите в следующем формате:
f([1,1,8,8])([0,6,9,9])
Обозначим входные данные как ((x1, y1), (x2, y2)), ((x3, y3), (x4, y4))
Если выполняется одно из следующих условий, вернуть первый прямоугольник как есть:
в противном случае
источник
f([0, 30, 10, 40])([5, 1, 6, 2])
должен вернуться,[[0, 30, 10, 40]]
но вместо этого возвращается[[0,30,5,40],[6,30,10,40]]
Java, 268 байт
Ungolfed
Передать ввод в качестве аргументов. пример
источник
Python 2 , 272 байта
Попробуйте онлайн!
Это работает путем проверки каждой ячейки внутри первого прямоугольника на левый = 1, неправильный = 4, правый = 2 и нижний = 8 по отношению к другой, и ИЛИ результат. Если другой не пересекает = 0 с первым, то возвращается оригинал, в противном случае возвращается некоторая комбинация левого, правого, верхнего и нижнего слоев с возможностью перекрытия.
источник