Ограничения.
* В 2D мире есть N непересекающихся чёрных прямоугольников.
* Чёрные прямоугольники не пересекаются и не должны пересечься далее никогда.
* Чёрные могут расширяться в любых направлениях, сдвигая границы от центра. Границу нельзя двигать к центру. Т.е. можно только так: верхнюю границу - вверх, нижнюю - вниз, левую - влево, правую - вправо. Можно не все границы. Можно вообще не расширяться.
* Нельзя плодить новые чёрные.
* Втыкаем в этот 2D мир произвольный красный прямоугольник в любое место. Чёрные расширяются как хотят, но соблюдая правило непересечения между собой, покрывают собой максимальную площадь на красном.
* не обязательно, чтобы в покрытии приняли участие все чёрные — можно обойтись хоть одним, если возможно. В некоторых случаях красный может целиком попасть в какой-то один чёрный, тогда задача покрытия красного решится сама собой и никто не будет расширяться.
Примеры ограничений в картинках.
Пример 1. Чёрным показаны существовавшие, красным - новый. Верхний может поехать вниз и закрыть красный, не пересекаясь с чёрным собратом. При этом, правый поехать никак не мог, т.к. задевал бы верхний.
Пример 2. Никто не может расшириться, чтобы накрыть красный. При попытке любого чёрного расшириться, произойдёт наезд на чёрного собрата (уменьшаться нельзя).
Пример 3. Чёрные могут втроем покрыть красный.
ЗАДАЧА
Доказать, что если у красного остаётся непокрытый кусок, этот кусок всегда прямоугольный при любом N чёрных. Ну или придумайте такую начальную расстановку чёрных и такой красный, при котором после попытки закрыть красный на нём останется непрямоугольный кусок.
