Главное меню портала
• О портале
• Архив задач
• Карта архива задач
• Результаты тестов
• Ошибки тестирования
• Преподаватели
• Библиотечка
Рейтинг у учителя
• Рейтинг на портале
Начинающему
• Работа с порталом
• Курс для начинающего
• Архив задач начинающего
Олимпиаднику
• Архив задач олимпиадника
Олимпиады
Дистанционные олимпиады
• Положение олимпиады
Новое сообщениеОтправленые
Загрузка...
Время на прохождение теста: 1 секунд(а/ы).
Имя входного файла: input.txt
Имя выходного файла: output.txt

Автор: Бельский Андрей Владимирович

Стадион
Совсем недавно стало известно, что в столице Байтландии, Байттауне, будет проводиться чемпионат мира по футболу. Однако в Байттауне нет ни одного футбольного стадиона. 

Мэрия Байттауна начала искать выход из сложившейся ситуации. Строительство нового стадиона было поручено известной Байтландской строительной компании. Проблема состояла в определении места для строительства стадиона. Так как данная задача оказалась сложной, было решено написать программу, решающую эту проблему и за помощью обратились к Вам – ведущему программисту Байтландии.

Вам дана карта Байттауна, которая представляет собой таблицу из N строк и M столбцов. Строки пронумерованы сверху вниз последовательно, начиная с 1. Столбцы пронумерованы слева направо последовательно, начиная с 1. Каждая ячейка таблицы имеет координаты (X, Y) – номер строки и номер столбца соответственно. В Байттауне расположены K прямоугольных парков, стороны которых параллельны границам карты. Парк не может частично содержать какие-то ячейки таблицы, другими словами парк занимаем прямоугольную часть таблицы. Каждый парк можно задать числами X1, Y1, X2, Y2, где (X1, Y1) – координаты левой верхней ячейки, и (X2, Y2) – координаты правой нижней ячейки таблицы, которые принадлежат парку. Каждая ячейка карты может принадлежать не более чем одному парку. 

Новый стадион должен иметь форму прямоугольника и прямоугольную часть таблицы размерами R строк и C столбцов. 

Мэрия Байттауна обеспокоена тем, чтобы строительство нового стадиона не привело к масштабной вырубке деревьев. Ваша задача – определить оптимальное расположение стадиона, то есть найти такое место для его строительства, чтобы количество ячеек, в которых необходимо вырубить деревья, было минимальным. Если таких мест для расположения стадиона несколько, то выберите из них то, у которого значение координаты X верхней левой ячейки стадиона минимально, если и таких расположений несколько, то дополнительно выберите с минимальным значением координаты Y.
Входные данные:
Первая строка входного файла содержит пять целых чисел, разделенных одиночными пробелами: N, M, K, R, C (1≤ R ≤ N ≤105, 1 ≤ C≤ M ≤105, 1 ≤ K ≤ 100) –размеры Байттауна. 

В следующих K строках задано по четыре целых числа, разделенных одиночными пробелами: X1,i Y1,i X2,i Y2,i (1 ≤ X1,i ≤ X2,i ≤ N, 1 ≤ Y1, количество парков в Байттауне и размеры нового стадиона соответственно. i ≤ Y2,i ≤ M) – координаты левой верхней и правой нижней ячеек прямоугольника, задающего i-ый парк.
Выходные данные:
Выходной файл должен содержать, в одной строке, три числа: номер строки и номер столбца левой верхней ячейки стадиона и минимальное количество ячеек, в которых необходимо вырубить деревья для строительства стадиона.

Примеры:
input.txt output.txt
1 5 3 2 2 2
2 2 2 2
4 2 4 2
1 1 1
2 5 5 5 3 2
1 1 1 5
2 1 5 1
5 2 5 5
2 5 4 5
3 3 3 4
2 2 1

Сложность задачи: 100%



Проверку могут осуществлять только зарегистрированные пользователи!


Разбор задачи
Пример 1.
Существует несколько расположений стадиона с одним вырубленных деревом. Координаты левой верхней ячейки стадиона в оптимальном расположении – (1,1).
Пример 2.
Координаты левой верхней ячейки в оптимальном расположении – (2,2). Будет вырублено одно дерево.
Показать обсуждение


На сайте гостей 22, зарегистрированных 0:
Сейчас онлайн только гости...
[Данные за последние 5 минут]