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

printЗадачи

954. Олимпиада

Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В 2107 году в региональном этапе олимпиады по программированию приняло участие уже не 25 школьников, а много тысяч. Но, как и сто лет назад, не все они были достаточно хорошо подготовлены. Поэтому членам жюри приходилось не раз подходить к участникам и объяснять, как прочесть входные данные из текстового файла. Это было не так просто сделать – ведь зал, где проводятся олимпиады в 2107 году, имеет размеры 10000 на 10000 метров, и одновременно могли просить помощи сотни участников, сидящих в разных концах зала. Было решено написать программу, оптимизирующую работу жюри. Задачу удалось формализовать следующим образом: `P` участников с известными координатами просят помощи, `J` членов жюри (`J\ <\ P`) находятся в этот момент в различных точках зала с известными координатами. Скорость перемещения членов жюри постоянна. Требуется направить членов жюри к `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

Пример вывода

4
Источник: Весенний турнир имени Мартовского Зайца, 2007
loading