АВТ
Language: Russian
English

Remote Training on Programming

Problems Online status Contests
Textbooks FAQ E-learning
For authors:
Register  ||  Login
 
Hello, Guest! Please login or register.

909. Cellular communications

Time Limit: 1 seconds
Memory Limit:65536KB
Points:100
View Problem Statistics Submit Problem added 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

 


View Problem Statistics Submit Problem discussion Author/source:
Problems from Contests / Vologda Students Contests / XIV InterUni Olympiad 2011 /
908. G - Coloring of patterns 909. 910. I - Rоuting 911. J - Weighting-2 912. X - Weighting
time generating 0.109 sec.
© Copyright VSU, AVT, Nosov D.A., Andrianov I.A.