Загрузка [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js
images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
06/04/2025 19:59:52

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

1066. НЛО

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

На поле фермера Джона приземлилось несколько летающих тарелок. Фермер хочет уничтожить оккупантов с помощью дезинтегратора, собранного его сыном для школьной научной выставки, но так как конструкция экспериментальная, можно сделать только один выстрел. Луч дезинтегратора распространяется по прямой и может уничтожить все тарелки на своем пути, достаточно всего лишь касания. Все тарелки имеют одинаковый размер, не пересекаются и не выходят за границу поля.
Какое максимальное количество НЛО сможет уничтожить фермер единственным выстрелом, если он может выбрать с какой точки на краю поля стрелять и в каком направлении?
В первой строке входного файла содержится два целых числа, разделенных пробелом – количество НЛО N (1 ) и радиус НЛО R (1\ ≤\ R\ ≤\ 100). Далее следует N строк, в каждой строке содержится два целых числа, разделенных пробелом – координаты центра i-го НЛО X_i,\ Y_i в диапазоне от R до 1000-R. Координаты левого нижнего угла поля – (0,0), а правого верхнего – (1000,1000).
В выходной файл вывести одно целое число – максимальное количество тарелок, уничтожаемых одним выстрелом.

Пример ввода

4 20
100 500
400 400
600 350
500 800

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

3
loading