| ENG RUS | Timus 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-х знаков после запятой. Примеры
Автор задачи: Александр Бикбаев Источник задачи: Десятый командный чемпионат школьников Свердловской области по программированию (16 октября 2004 года) |