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

Экскурсия

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

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

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

Формат входного файла input.txt
Первая строка - целые числа M, L, N, K (1 <= M <= 20, 1 <= L, N <= 1000, 1 <= K <= 3) - количество гостей города, количество "горизонтальных" и "вертикальных" улиц, и максимальное количество кварталов, которое гости города могут пройти до места сбора.
Каждая из следующих M строк содержит по два целых числа через пробел - начальные координаты каждого из гостей города в формате <номер "горизонтальной" улицы>, <номер "вертикальной" улицы>

Формат выходного файла output.txt
Первая строка содержит целое число G - минимально возможное количество гостей города, которые не смогут собраться на трех перекрестках (0 в случае, если найдется три или менее перекрестков, на которых они смогут собраться).
Вторая строка содержит целое число P - количество перекрестков, на которых соберутся гости города (1 <= P <= 3), затем - три пары целых чисел, указывающих координаты перекрестков (сначала номер "горизонтальной" улицы, затем номер "вертикальной" улицы). Все числа отделяются друг от друга пробелом. Никакие два перекрестка не должны совпадать.
Если решений несколько, выведите любое из них.

Дополнение.
Решение, корректно работающее при 1 <= L, N <= 10, может набрать от 30 баллов

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

Пример выходного файла
0
3 1 2 2 8 5 4

Сдать задачу

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