|
Remote Training on Programming
|
||||||||||
|
|
|||||||||||
| Hello, Guest! Please login or register. |
1864. Mobile communications
|
| View Problem Statistics | Submit | Problem added debug |
|
Через отдалённую местность проходит автомобильная трасса. На карте трасса выглядит как прямая линия, совпадающая с осью OX. В некоторых точках этой трассы установлено N станций сотовой связи. Каждая станция имеет одинаковый радиус действия, равный R. В окрестностях трассы находятся M деревень. Размеры всех деревень столь малы, что их можно считать точками. Будем говорить, что деревня входит в зону действия станции, если расстояние от этой деревни до станции не превышает R. Определите для каждой станции, сколько деревень входят в её зону действия. Входные данные В первой строке входных данных записаны три натуральных числа N, M и R — число станций, число деревень и радиус действия станций. В следующих N строках записано по одному целому числу в порядке возрастания — x-координаты станций (все их y-координаты равны нулю). В следующих M строках записано по два целых числа — координаты x и y каждой деревни. Никакие две деревни не находятся в одной точки. Все координаты не превосходят по модулю 109. Выходные данные Выведите N целых чисел, каждое в отдельной строке — количество деревень в зоне действия первой, второй и так далее станций. Система оценки Подзадача 1 (40 баллов): 1 ≤ N, M ≤ 1000, 1 ≤ R ≤ 109 Подзадача 2 (30 баллов): 1 ≤ N, M ≤ 105, 1 ≤ R ≤ 500 Подзадача 3 (30 баллов): 1 ≤ N, M ≤ 105, 1 ≤ R ≤ 109 Пример Входные данные 2 3 3 Выходные данные 2 Примечание Ниже приведена иллюстрация к примеру из условия.  Здесь одна из деревень попадает в зону действия обеих станций, поэтому при подсчёте она учитывается для каждой станции.
|
| View Problem Statistics | Submit | Problem discussion | Author/source: |
| 1863. 4 - Take more | 1864. |
| time generating 0.109 sec. |
| © Copyright VSU, AVT, Nosov D.A., Andrianov I.A. |