|
Задача Торговые Агенты (AGENTS)
Отдел доставки фирмы "Рога и Копыта" обслуживает торговые точки. Каждый день товар завозится в одну из них. График завоза по дням составлен заранее, причем в этом графике точки могут повторяться.
Два агента с машинами распределили заказы между собой. Каждый день один из них завозит товар в очередную торговую точку и остается в ней, а другой никуда не перемещается. Работа агентов спланирована так, чтобы суммарный расход горючего был минимальным. Торговые точки заданы своими координатами. Из точки в точку агенты перемещаются по прямой. Перед началом работы агенты находятся в точке плоскости с координатами (0,0).
Напишите программу AGENTS, которая читает входные данные с клавиатуры : число торговых точек N и N пар вещественных чисел (X1 ,Y1 ), (X2 ,Y2 ), ... (XN
,YN )
- координаты 1-ой, 2-ой, …, N
-ой торговых точек, затем число дней в графике
M и M чисел K1
K2 ,...
KM - номера точек,
которые нужно посетить в 1-ый, 2-ой, …, M -ый день.
Программа должна определить суммарный пробег машин S
с точностью до ε =10 -5
и вывести его на эеран .
Ограничения:
1<= N <=10,
-1000.0<= Xk
Yk <=1000.0
(k = 1,2,...,N)
1<= M <=10000,
-1000.0<= Kj <=N
(j = 1,2,...,M)
Формат ввода/вывода:
ввод:
N
X1 Y1
X2 Y2
...
XN YN
M
K1
K2
...
KM
| вывод:
S
|
Пример:
ввод:
3
3.0 4. 0
1.0 4.0
4.0 1.0
5
2
3
1
3
2
| вывод:
12.2462112512
|
|
