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

printЗадачи

1997. GPS

Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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
loading