НачалоПодразделы
Другие разделы
Дата и время
05/04/2025 20:25:48
1588. Марсианский монитор
Марсианский монитор
Сокращение перебора с помощью идеиОлимпиадные задачи на русском языке
| 04/07/2011 | Лето 2011 - дорешивание (03D) |
| 06/07/2011 | Лето 2011 - 3 (D) |
Ограничения: время – 1s/2s, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Марсианский институт разработал новую модель черно-белого компьютерного монитора
с разрешением W пикселей по горизонтали и H пикселей по вертикали.
Новый монитор очень дёшев в производстве, но имеет один конструктивный недостаток – если какой-либо из пикселей стал белым,
то все пиксели, находящиеся на расстоянии, меньшем или равном L, белыми стать уже не могут.
(Расстояние между пикселями c координатами (x1, и (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
