Задача D. Космические исследования
Первоисточник: Всероссийская олимпиада школьников по информатике 2010/2011 учебного года. Региональный этап, первый тур, 21 января 2011 г.
URL первоисточника: http://neerc.ifmo.ru/school/archive/2010-2011/ru-olymp-regional-2011-archive.rar
Задачу добавил: alef
Успешно сдано решений: 3
Ограничение по времени: 4 с
Ограничение по памяти: 256 Мб
Отделу космических исследований поступило задание сфотографировать из космоса n объектов в заданной области. Область имеет форму квадрата размером 50×50 километров. Если разделить ее на квадраты размером 1×1 километр, то интересующие отдел объекты окажутся в центрах некоторых единичных квадратов.
Введем систему координат, направив ось OX с запада на восток и ось OY с юга на север. Тогда каждому единичному квадрату будут сопоставлены координаты в диапазоне от 1 до 50, как показано на рисунке ниже.
Для космической съемки используется специальный фотоаппарат высокого разрешения, установленный на космическом спутнике. Фотоаппарат может делать снимки квадратных участков земной поверхности размером k × k километров. Исходно аппарат наведен на юго-западный угол заданной области, то есть, если сделать снимок, на нем будут видны единичные квадраты с координатами x и yот 1 до k километров.
С помощью специальных двигателей можно изменять орбиту спутника, что приводит к изменению участка съемки. За один день орбиту спутника можно изменить таким образом, что участок съемки сместится либо на один километр на запад, либо на один километр на восток, либо на один километр на север. Переместить участок съемки на юг невозможно. Непосредственно между перемещениями спутника можно сделать снимок, временем съемки можно пренебречь.
Руководство отдела заинтересовалось вопросом: за какое минимальное количество дней можно сделать снимки всех объектов заданной области.
Требуется написать программу, которая по заданному расположению объектов и размеру снимка k определит минимальное время, за которое можно сделать снимки всех объектов заданной области.
Первая строка входного файла содержит два целых числа: n и k (1 ≤ n ≤ 1000, 1 ≤ k ≤ 5).
Следующие n строк содержат по два целых числа: xi и yi — координаты объектов в заданной области (1 ≤ xi, yi ≤ 50).
Формат выходного файла output.txt
В выходном файле должно содержаться одно целое число: минимальное количество дней, которое требуется для получения снимков всех объектов в заданной области
Пример входного файла - 1
4 1
1 1
10 2
1 3
10 4
Пример выходного файла - 1
30
Пример входного файла - 2
4 2
1 1
10 2
1 3
10 4
Пример выходного файла - 2
10
Пример входного файла - 3
1 1
1 1
Пример выходного файла - 3
0
Пример входного файла - 4
3 3
3 3
3 6
6 3
Пример выходного файла - 4
7
Пояснения к примерам:
В первом примере возможна следующая последовательность действий: сделать снимок, 9 раз сместиться на восток, сместиться на север, сделать снимок, 9 раз сместиться на запад, сместиться на север, сделать снимок, 9 раз сместиться на восток, сместиться на север, сделать снимок. Всего требуется 30 перемещений участка съемки.
Во втором примере объекты расположены там же, но размер снимка больше, поэтому можно действовать так: сделать снимок, сместиться на север, сделать снимок, 8 раз сместиться на восток, сделать снимок, сместиться на север, сделать снимок. Всего требуется лишь 10 перемещений участка съемки.
В третьем примере перемещать участок съемки не требуется, можно просто сделать снимок.
Четвертый пример соответствует приведенному выше рисунку.
Примечание
Правильные решения для тестов, в которых k = 1, будут оцениваться из 30 баллов.
Правильные решения для тестов, в которых k > 1 и 1 < n ≤ 15, будут оцениваться из 30 баллов.