ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Соревнование школьников. Октябрь 2004

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

E. Владислава

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
— Мы называем этот спутник Владя. Как вам известно, у Владиславы есть еще один спутник, тоже искусственный и тоже неземного происхождения. Он меньше по размерам. Мы называем его Слава. Вы понимаете? Планета называется "Владислава". Естественно назвать два ее спутника "Владя" и "Слава". Не так ли?
— Да, конечно, — сказал Горбовский. Это изящное рассуждение было ему знакомо. Он слышал его в третий раз. — Это вы очень остроумно предложили, Август. Владя и Слава — Владислава. Прекрасно!
— У вас на Земле, — продолжал Бадер неторопливо, — эти спутники называют "Игрек-один" и "Игрек-два", соответственно — Владя и Слава. Но мы - мы называем их иначе. Мы называем их Владя и Слава.
Он строго поглядел на Валькенштейна. Валькенштейн играл желваками на скулах. Насколько было известно Валькенштейну, "мы" — это был сам Бадер и только Бадер."
На планете Владислава обнаружены артефакты внеземных цивилизаций в количестве N штук.
Исследовательский звездолет вышел на орбиту планеты и запустил автоматические зонды, которые обнаружили, что из-за неровного рельефа атмосферный катер может сесть только в одной из M точек планеты. Так как передвижение по планете происходит медленно, нужно для каждого артефакта найти ближайшую посадочную площадку.

Исходные данные

В первой строке записаны числа N и M (1 ≤ N, M ≤ 5000) — количество артефактов и точек посадки соответственно. Затем записан радиус планеты R — положительное действительное число; R ≤ 1000. Далее следует M строк, в каждой из которых записаны широта и долгота одной из точек посадки Wi, Li — действительные числа |Wi| ≤ 90, |Li| ≤ 180. В следующих N строках записаны координаты артефактов — широта и долгота wi, li — действительные числа |wi| ≤ 90, |li| ≤ 180. Все действительные числа округлены до 6 знаков после десятичной точки.

Результат

Следует вывести ровно N строк. В i-й строке должно быть записано расстояние от i-го артефакта до ближайшей точки посадки с точностью до 2-х знаков после запятой.

Примеры

исходные данныерезультат
1 2
1
0 0
1 1
0 0
0.00
2 1
1
0 0
0 90
0 45
1.57
0.79
Автор задачи: Александр Бикбаев
Источник задачи: Десятый командный чемпионат школьников Свердловской области по программированию (16 октября 2004 года)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1331. Владислава