За шесть с половиной лет, прошедших после первых экспериментальных джинн-бомбардировок,
Питирим Шварц достиг значительных успехов. Его новейшая разработка —
бутылка с ифритом — предназначена специально для
бомбардировки крупных городов. С помощью нескольких таких бутылок можно,
например, стереть с лица земли все n крупных городов соседнего государства…
Увы, бутылок с ифритами у Питирима совсем немного,
поэтому он поручил программисту Привалову вычислить минимальное количество
бутылок, необходимое для уничтожения всех n городов.
Для удобства прицеливания планируется сбрасывать бутылки только непосредственно на города.
Ифрит разрушает все города, находящиеся на расстоянии не более r от точки падения бутылки.
Радиус поражения столь велик, что города можно считать точками на плоскости.
Исходные данные
В первой строке записаны целые числа n и r (1 ≤ n ≤ 30;
1 ≤ r ≤ 1000).
В i-й из следующих n строк записаны координаты i-го города —
два целых числа в пределах от 0 до 1000.
Результат
В первой строке выведите минимальное количество бутылок с ифритами,
необходимых для разрушения всех городов.
В следующей строке через пробел выведите номера
городов, на которые нужно сбросить эти бутылки.
Если существует несколько способов сбросить бутылки, можно вывести любой из них.
Пример
исходные данные | результат |
---|
4 50
10 10
500 500
501 501
999 999
| 3
1 3 4
|
Автор задачи: Игорь Андрианов
Источник задачи: XII открытое личное первенство УрГУ (19 марта 2011)