Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1997. GPS
Вычислительная геометрияСканирование, метод двух указателей
Олимпиадные задачи на русском языке
| 20/10/2013 | Региональные отборочные командные соревнования для школьников (G) |
| 24/10/2013 | Занятие 7 для продолжающих (B) |
| 19/02/2014 | Занятие 14 (D) |
Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Многие современные мобильные устройства имеют GPS, позволяющую определить координаты местоположения
устройства. Качество и время определения местоположения зависит от количества спутников, расположенных
строго выше горизонта, так как Земля экранирует сигнал от спутников.
Для упрощения задачи рассмотрим двумерный случай. Планета представляется в этом случае окружностью с центром
в начале координат, а линией горизонта является касательная к этой окружности.
Напишите программу, которая по текущему положению спутников определяет минимальное и максимальное количество спутников, видимых в
каких-либо точках на двумерной планете.
Первая строка ввода содержит два целых числа — количество спутников `N` (`2\ ≤\ N\ ≤\ 100\ 000`) и радиус планеты `R` (`1\ ≤\ R\ ≤\ 1000`).
Далее следует `N` строк с координатами спутников `X_i`, `Y_i` (`R^2\ <\ X_i^2+Y_i^2\ ≤\ 100*R^2`).
Вывести два числа – минимальное и максимальное количество спутников, видимых над горизонтом
где-либо на поверхности планеты.
Пример ввода
4 10 -20 -20 20 20 -20 20 20 -20
Пример вывода
1 2
