Модуль: 11.1G Динамическое программироварие. Часть 7. Интересные задачи


Задача

3 /5


Ускорители для Деда Мороза


Задача

Дед Мороз за ночь должен посетить N городов. У него есть двумерный план расположения всех городов. План нарисован в декартовой системе координат, в которой точкой (0, 0) обозначено место старта Деда Мороза. Каждый город на плане отмечен точкой с координатой (Xi, Yi). Также на карте обозначены M точек с координатами (Pi, Qi), в которых расположены ускорители. Чтобы успеть разнести все подарки, Дед Мороз может воспользоваться ускорителем, который увеличивает его скорость в два раза (а может им и не пользоваться).

Дед Мороз в Новогоднюю ночь начинает с места старта, посещает все N городов и возвращается обратно.

Начальная скорость Деда Мороза равна 1. Найдите наименьшее время, необходимое Деду Морозу, чтобы посетить все города и вернуться обратно. Временем, при котором он раскладывает все подарки будем пренебрегать!



Входные данные
Первая строка входных данных содержит два целых числа N и M (1 <= N <= 12, 0 <= M <=5). Следующие N строк содержат координаты городов (Xi, Yi). Далее идут M строк с координатами ускорителей (Pi, Qi). Все координаты различны и среди них нет координаты (0, 0).

Выходные данные
Выведите ответ на задачу, с точностью не менее 6 знаков после запятой.
 
 
Примеры
Входные данные Выходные данные Примечание
1 2 1
1 1
0 1
1 0
2 1
1 1
0 1
1 0
Вот один из оптимальных способов разнести все подарки
  • Пройти расстояние 1 от начала координат до ускорителя 1 со скоростью 1, затратив время 1.
  • Пройти расстояние 1 от ускорителя 1 до города 1 со скоростью 2, затратив время 0,5.
  • Пройти расстояние 1 от города 1 до города 2 со скоростью 2, затратив время 0,5.
  • Пройти расстояние 1 от города 2 до начала координат со скоростью 2, затратив время 0,5.
2 2 1
1 1
0 1
100 0
3.4142135624 Вот один из оптимальных способов разнести все подарки
  • Пройти расстояние 1.41... от начала координат до города 1 со скоростью 1, затратив время 1.41....
  • Пройти расстояние 1 от города 1 до города 2 со скоростью 1, затратив время 1.
  • Пройти расстояние 1 от города 2 до начала координат со скоростью 1, затратив время 1.
3 1 2
4 4
1 0
0 1
4.3713203436 Вот один из оптимальных способов разнести все подарки
  • Пройти расстояние 1 от начала координат до ускорителя 1 со скоростью 1, затратив время 1.
  • Пройти расстояние 1,41... от ускорителя 1 до ускорителя 2 со скоростью 2, затратив время 0,707....
  • Пройти расстояние 5 от ускорителя 2 до города 1 со скоростью 4, затратив время 1,25.
  • Пройти расстояние 5,65... от города 1 до начала координат со скоростью 4, затратив время 1,41....

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Python2
Комментарий учителя