20 кто правильно напишет ограничение по времени на тест1 секунда ограничение по памяти на тест256 мегабайт ввод стандартный ввод вывод стандартный вывод амира получила в подарок прямоугольник в свой долгожданный день рождения. прямоугольник имеет размеров w x h, где w и h - целые числа. мухитали решил подарить ей еще один подарок - два квадратика. увидев что теперь у нее есть целых 3 фигуры, она решила их использовать для создания нового искусства вместе с мухитали. они решили приклеить квадратики на ее прямоугольник таким образом, чтобы они не пересекались между собой по ненулевой площади дабы избежать смешивания цветов, а так же не выходили за пределы самого прямоугольника. для удобства они могут резать квадратики до любых размеров (даже нулевых), главное чтобы они имели размеры не больше чем параметры оставшегося прямоугольника и при этом не потеряли свойства квадрата. для большего удовольствия, амира и мухитали хотят чтобы эти два квадратика покрыли как можно большую площадь ее прямоугольника. ей найти это значение. входные данные в единственной строке входных данных находятся два целых числа w и h (1≤w,h≤109) - параметры прямоугольника. выходные данные выведите одно целое число - максимальную площадь подпрямоугольника, которую амира и мухитали смогут покрыть с двух квадратиков. система оценки данная содержит четыре , в каждой выполняются ограничения из условий: 1. 1≤w,h≤5. оценивается в 29 . 2. 1≤w,h≤100. оценивается в 21 . 3. 1≤w,h≤104. оценивается в 20 . 4. 1≤w,h≤109. оценивается в 30 .
Для решения этой задачи, нам необходимо выяснить, как можно эффективно использовать два квадратика на прямоугольнике.
Рассмотрим два случая:
1. w и h являются одинаковыми числами.
Если ширина и высота прямоугольника одинаковы, то самым эффективным способом будет разделить прямоугольник на две части по диагонали. Таким образом, мы получим два прямоугольника равной площади, в которые можно вписать квадратики.
2. w и h являются разными числами.
Если ширина и высота прямоугольника различаются, то возможны два варианта:
а) Вписать квадратик в одну из сторон прямоугольника.
б) Вписать квадратик в угол прямоугольника таким образом, чтобы одна сторона квадратика была параллельна одной из сторон прямоугольника.
- В случае а) мы можем вписать квадратик либо в сторону w, либо в сторону h (в зависимости от того, какая сторона больше). При этом, максимальная площадь подпрямоугольника будет соответствовать площади оставшегося отрезка прямоугольника после вырезания квадратика.
- В случае б) мы можем вписать квадратик в угол прямоугольника так, чтобы одна из его сторон была параллельна одной из сторон прямоугольника (см. рисунок). При этом, максимальная площадь подпрямоугольника будет соответствовать площади оставшихся двух прямоугольников после вырезания квадратика.
w
h_____________________
| | |
| | |
| | |
| | |
| | |
|--------|--Квадратик |
| | |
| | |
| | |
|_____ |_________ |
h w
Таким образом, для решения задачи, мы должны:
1) Сравнить значения w и h.
2) Если они равны, вернуть произведение w и h, деленное на 2.
3) Если они различны, найти максимум из следующих вариантов:
а) Вписать квадратик в одну из сторон прямоугольника и вычислить площадь оставшегося отрезка прямоугольника.
б) Вписать квадратик в угол прямоугольника и вычислить площадь оставшихся двух прямоугольников.
Пример решения для w = 6 и h = 9:
1) w и h разные числа, поэтому переходим к шагу 3.
2) Вариант "а": Вписываем квадратик в сторону w. Получаем оставшийся прямоугольник с размерами 6 x (9-6) = 6 x 3.
Площадь этого прямоугольника равна 6 x 3 = 18.
3) Вариант "б": Вписываем квадратик в угол прямоугольника. Получаем два оставшихся прямоугольника с размерами 6 x (9-6) = 6 x 3.
Площадь каждого из этих прямоугольников равна 6 x 3 = 18.
Максимальная площадь будет соответствовать площади двух прямоугольников, то есть 18 + 18 = 36.
Ответ: Максимальная площадь подпрямоугольника, которую можно покрыть двумя квадратиками, равна 36.