Увидел неожиданно низкий процент решаемости у лёгкой задачи, давайте разбираться, как её решать. Читаем условие, смотрим картинку и примеры, понимаем:
Тема задачи - "Двумерные массивы" - и очень маленькие ограничения подсказывают, что можно завести массив с размерами поля и для каждого участка делать заполнение соответствующего прямоугольника. И для вычисления ответа достаточно будет просуммировать числа, попавшие в прямоугольник, подобранный для строительства.
Но на мой взгляд такое решение ничуть не легче, чем более правильное и быстрое. Поэтому давайте изучать хорошее.
В этой задаче нам надо вычислять площадь пересечения двух прямоугольников. Заметим, что пересечение двух прямоугольников - прямоугольник, а значит площадь равна произведению длины на ширину. А значит двумерную задачу можно свести к двум одномерным, а потом перемножить ответы:
Функция get_len будет принимать границы двух отрезков на прямой и вычислять длину их пересечения. Важным замечанием является то, что координаты должны быть заданы в порядке слева направо. То есть сначала левая координата первого отрезка, затем правая координата первого отрезка, затем в том же порядке координаты второго отрезка.
Ограничение нулём снизу на случай отсутствия пересечения.
Теперь у нас есть всё для решения задачи. Считаем и подготовим входные данные:
В строках 16-19 как раз выполняется обмен значений координат так, чтобы они подходили под условие, которое требуется функции get_len. Обратим внимание на то, что эти операции разрешены, потому что обмен x-ов приводит лишь к отражению прямоугольника по горизонтали (а y-ов - по вертикали). То есть прямоугольник по-прежнему будет задан координатами противоположных углов, но такими отображениями мы приводим к тому, что все прямоугольники будут заданы левым нижним и правым верхним углами. И это наиболее удобная форма хранения прямоугольников, которую рекомендую использовать всегда.
В решении я увеличил n на единицу и считал прямоугольник, который выбрали для строительства в те же самые списки с остальными участками потому что он ничем от них не отличается (да, при этом немного страдает понимание кода, но тут всего 25 строк). Зато теперь можно найти сумму площадей пересечения всех прямоугольников с -1-ым (потому что в Python списки циклические):
Несложное решение за линейное, если бы участок для строительства вводился в первую очередь, то вообще можно было бы обойтись без массивов.
Думаю, что низкая решаемость обусловлена те, что многие забывают упорядочить координаты прямоугольников и привести их к виду "левый нижний и правый верхний". Потому что в решении с двумерным массивом в таком случае были бы циклы, которые не выполняли ни одной итерации.
Предыдущий выпуск: Задача 628. Clear World and Brothers
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.
