Подразделы

Другие разделы

Дата и время

04/04/2025 03:36:12

Авторизация

1588. Марсианский монитор

Ограничения: время – 1s/2s, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Марсианский институт разработал новую модель черно-белого компьютерного монитора с разрешением

$W$ пикселей по горизонтали и

$H$ пикселей по вертикали.

Новый монитор очень дёшев в производстве, но имеет один конструктивный недостаток – если какой-либо из пикселей стал белым, то все пиксели, находящиеся на расстоянии, меньшем или равном

$L$ , белыми стать уже не могут. (Расстояние между пикселями c координатами

$(x_1,\ y_1)$ и

$(x_2,\ y_2)$ считается по обычной формуле –

$sqrt{(x_1\ -\ x_2)^2\ +\ (y_1\ -\ y_2)^2}$ ).

На монитор, первоначально полностью чёрный, последовательно выводится

$N$ белых пикселей. Определите, какие из этих пикселей фактически станут белыми.

Входной файла целые числа

$N\ W\ H\ L$ (

$1\ ≤\ N\ ≤\ 5*10^4$ ,

$1\ ≤\ W\ ≤\ 2560$ ,

$1\ ≤\ H\ ≤\ 2048$ ,

$0\ ≤\ L\ ≤\ 25$ ). Далее идут

$N$ пар целых чисел

$X_i\ Y_i$ (

$1\ ≤\ X_i\ ≤\ W$ ,

$1\ ≤\ Y_i\ ≤\ H$ )- координаты

$i$ -го выводимого пикселя.

Выходной файл должен содержать целое число

$M$ – количество отображённых пикселей. Далее должны идти

$M$ целых чисел

$a_j$ – порядковые номера отображённых пикселей, в возрастающем порядке. Пиксели нумеруются с единицы.

Пример ввода 1

3 10 10 2
1 1  1 3  3 2

Пример вывода 1

2
1 3

Пример ввода 2

8 13 9 3
1 1  2 1  3 3  3 6  7 3  6 3  7 7  7 6

Пример вывода 2

4
1 4 5 7

Источник: http://imcs.dvgu.ru/cats/ Весенний турнир, 2011

04/07/2011	Лето 2011 - дорешивание (03D)
06/07/2011	Лето 2011 - 3 (D)

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

1588. Марсианский монитор

Марсианский монитор