A. Олимпиада
Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод ![Копировать номер copy](/images/simple/b_copy.png)
Послать решение Blockly Посылки Темы Где Обсудить (0)
В 2107 году в региональном этапе олимпиады по программированию приняло участие уже не 25 школьников, а много тысяч.
Но, как и сто лет назад, не все они были достаточно хорошо подготовлены. Поэтому членам жюри приходилось не раз подходить
к участникам и объяснять, как прочесть входные данные из текстового файла. Это было не так просто сделать – ведь зал,
где проводятся олимпиады в 2107 году, имеет размеры 10000 на 10000 метров, и одновременно могли просить помощи сотни
участников, сидящих в разных концах зала. Было решено написать программу, оптимизирующую работу жюри.
Задачу удалось формализовать следующим образом: P участников с известными координатами просят помощи, J членов жюри (J )
находятся в этот момент в различных точках зала с известными координатами. Скорость перемещения членов жюри постоянна.
Требуется направить членов жюри к J различным участникам таким образом, чтобы последний из них добрался до своего участника
за наименьшее возможное время. К сожалению, искусство программирования в 2107 году пришло в упадок и никто из членов жюри
не смог написать такую программу. Лишь председатель, ещё помнивший те легендарные времена, когда команда DesperaDOS легко
решала целых три задачи в NEERC, закодировал переборный алгоритм. Но время работы этого алгоритма превышало время
проведения олимпиады. И тогда жюри решило обратиться к Великим Программистам Прошлого (проблема путешествий во времени,
как вам известно, в 2107 году уже решена). Оно выбрало самый известный из турниров, проводившихся на Земле в начале XXI века – Весенний турнир имени Мартовского Зайца.
И вот задача перед вами.
Ввод
В первой строке входного файла записаны три целых числа: J – количество свободных в данный момент членов жюри, P – количество участников, просящих помощи (0\ <\ J\ <\ 100, J\ <\ P\ <\ 200) и V – скорость передвижения членов жюри в м/с. Во второй строке записано 2*J целых чисел x_i,\ y_i – координаты членов жюри (0\ ≤\ x_i,\ y_i\ ≤\ 10000).
В третьей строке в том же формате записаны координаты участников.
Вывод
Запишите в выходной файл минимальное время, за которое последний из членов жюри достигнет своего участника, округлённое в большую сторону.
Пример ввода
3 4 10
0 0 25 25 50 0
0 50 50 50 25 0 75 0
Источник: Весенний турнир имени Мартовского Зайца, 2007