Task 64. Одинаковый периметр
UniLecsЗадача: дана геометрическая фигура в виде квадратов (зеленого цвета), каждый зеленый квадрат имеет хотя бы одну общую точку хотя бы с одним другим зеленым квадратом. Исходная фигура является связной.
Исходная фигура задается массивом точек (-100 <= x,y <= 100) левых нижних углов зеленых квадратов.
Нужно дорисовать заданную фигуру максимальным кол-вом квадртов желтого цвета таким образом, чтобы периметр новой фигуры оставался таким же.
Входные данные: массив координат левых нижних углов зеленых квадратов.
Вывод: кол-во желтых квадратов.
Написать программу, ктр по заданным координатам исходных квадратов найдет максимальное кол-во желтых квадратов, ктр нужно дорисовать так, чтобы периметр новой фигуры не изменился.
Пример:
[ { x: 1, y: 1}, { x: 2, y: 1 }, { x: 2, y: 2 }]
Вывод 1.
Идея: заведем отдельный массив для информации о зеленых квадратах
res[Max, Max], Max = 200.
Т.к. по условию координаты могут быть отрицательными, то совершим перенос координат так, чтобы центр (0,0) перешел в центр например (100, 100).
Дальше найдем периметр образовавшейся зеленой замкнутной фигуры p. Для этого найдем координаты левого нижнего (minX, minY) и правого верхнего (maxX, maxY) прямоугольника, ограничивающего зеленую область. Очевидно, что все пустые квадраты в ограничивающем прямоугольнике можно дорисовать желтым, т.к. от этого периметр новой фигуры не увеличиться (он может или не измениться, или уменьшится, если в зеленой фигуре есть дырки).
Если периметр ограничивающего прямоугольника pp меньше периметра зеленой области p, то следует дорисовать максимальное кол-во желтых квадратов так, чтобы указанные периметры сравнялись. Очевидно, что значения периметров всегда четные. Если к прямоугольнику дорисовать колонку или ряд желтых квадратов, то периметр полученного прямоугольнику увеличится на 2. Поскольку условие задачи требует дорисовать максимальное кол-во желтых квадратов, то каждый раз к имеющемуся прямоуголнику (изначально им является ограничивающий прямоугольник) следует пририсовать ряд желтых квадратов к той стороне, ктр длинее.
Для наглядности, продемонстрирую следующий пример:
Периметр ограничивающего прямоугольника размером 5 * 4 равен 18, что меньше периметра зеленой области, равной 26.
Добавляем сначала две колонки желтых квадратов справа, после чего размер прямоугольника стал равен 5 * 6. Теперь длина прямоугольника стала больше ширины. Добавляем строку желтых квадратов снизу. После чего все равно что добавить – или дополнительную строку, или дополнительный столбец. Периметр полученного прямоугольника сравнялся с периметром начальной зеленой области.
Реализация:
https://gist.github.com/unilecs/70560b48ad6801b43c454b41e14c1044
Тест: