АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

909. Сотовая связь

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил Igor Andrianov

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

Радиус действия станций и координаты деревень известны. Все деревни находятся на плоской равнине без препятствий для радиосигнала, то есть радиус действия станции не зависит от места её установки. Если деревня оказывается ровно на границе зоны действия какой-то станции, то считается, что связь в ней есть.

Требуется обеспечить связью всех жителей, построив для этого наименьшее количество станций.

В первой строке входного файла записаны через пробел два целых числа: N (1  N  30) — количество деревень и R (1  R  1000) — радиус действия станций. В каждой из следующих N строк записаны координаты очередной деревни в декартовой системе (два целых числа x и y через пробел в диапазоне от 0 до 1000).

В первой строке выходного файла выведите целое число M — минимальное количество станций, которое потребуется построить. В следующей строке через пробел выведите M чисел — номера деревень, в которых нужно построить станции. Нумерация деревень от 1 до N в соответствии с порядком, в котором они шли во входном файле.

Пример

Поток ввода

Поток вывода

4 50

10 10

500 500

501 501

999 999

3

1 3 4

 


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Межвузовские олимпиады / XIV Межвузовская олимпиада 2011 /
908. G - Покраска паттернов 909. 910. I - Мaршрутизация 911. J - Взвешивание-2 912. X - Взвешивание
 
время генерации 0.109 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.