Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Пирожные

Задачу добавил: alef

Успешно сдано решений: 13

По случаю приезда M гостей города S один из их друзей испек большой прямоугольный торт и щедро украсил его кремовыми розочками (будем считать, что все розочки одинакового размера и каждая занимает собой квадрат на поверхности торта - см. рис.). Когда приготовление было закончено, оказалось, что такой большой торт не получается уместить на столе вместе с остальными блюдами.
У автора торта имеется квадратная форма для вырезки пирожных, и он решил ею воспользоваться, разделив с ее помощью торт на порции. Но еще не принявшись за работу, он вспомнил, что один из M гостей города S совсем не любит кремовые розочки, и всегда старается отрезать себе такой кусочек, на котором их нет.
Ваша задача - выяснить, можно ли вырезать из торта такой кусочек, на котором не будет ни одной розочки. Форму разрешается помещать на торт только так, чтобы ее стороны были параллельны сторонам торта.

Формат входного файла input.txt
Первая строка - целые числа M, N, R, K, где
1 <= M, N <= 1000 - длина и ширина торта
1 <= R <= min(M,N) - длина стороны квадрата, в котором располагается розочка
1 <= K <= min(M,N) - длина стороны формы для вырезки пирожных
Вторая строка - целое число F (1 <= F <= 10000) - количество розочек на торте. Гарантируется, что никакие две розочки не перекрываются
Каждая из следующих F строк содержит целые координаты левого верхнего угла очередной розочки Xj и Yj (j = 1, 2, ..., F) через пробел

Формат выходного файла output.txt
Первая строка - два целых числа через пробел - координаты X и Y левого верхнего угла квадрата со стороной K, в котором не будет ни одной розочки
Если решений несколько, выведите любое из них. Если же решений нет, выведите в качестве ответа пару: -1 -1

Пример входного файла
12 7 2 3
6
8 2
5 4
10 6
3 2
8 7
3 6

Пример выходного файла
10 3

Сдать задачу

Задать вопрос жюри по этой задаче