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

Снежная крепость (35 баллов)

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

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

После встречи нового года друзья вышли на улицу. Погода - замечательная, много снега. И кому-то пришла в голову идея построить снежную крепость. Для этого друзья принялись скатывать снег в шары, и чрезвычайно этим увлеклись. Получилось так, что во дворе (который ради простоты будем считать прямоугольником размером P x Q метров) оказалось М больших и тяжелых скатанных шаров, расположенных в разных местах. А для построения крепости достаточно K шаров. Поэтому нужно выбрать участок, на котором будет построена крепость, таким образом, чтобы он имел наименьшую площадь (тогда трудозатраты на перемещение шаров будем считать наименьшими).


Формат входного файла input.txt
Первая строка - два целых числа P и Q - размеры двора (1<=P,Q<=200)
Вторая строка - два целых числа M и K (1<=K<=M<=100) через пробел: количество существующих шаров и количество шаров, достаточное для построения крепости.
Следующие M строк - пары целых чисел Sx,Sy, обозначающие координаты каждого из M шаров (1<=Sx<=P, 1<=Sy<=Q).


Формат выходного файла output.txt
Целое число - минимально возможная площадь участка, на котором расположены K шаров

Пример входного файла
200 200
1 1
5 200


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

Сдать задачу

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