eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Сомневающееся начальство

Сомневающееся начальство

Лимит времени 2 секунды
Лимит использования памяти 256 MiB

На координатной прямой заданы N вершин, и надо многократно находить кратчайший среди путей, проходящих через эти вершины и и возвращающихся в начальную.

prb807

Длина пути равна сумме длин составляющих его отрезков, длину одного отрезка можно посчитать по формуле

Зачем один и тот же путь находить многократно? А он не один и тот же - начальство никак не определится, какие из этих N вершин в самом деле нужны, а какие нет. И поэтому приходится для одного и того же набора вершин обрабатывать разные запросы, отличающиеся набором нужных вершин. В каком порядке обходить нужные вершины и какую из них выбрать в качестве начальной (она же конечная), выбирает не начальство, а тот, кто ищет минимальный путь.

Входные данные

В первой строке задано количество вершин N (4 ≤ N ≤ 17). В каждой из последующих N строк заданы по два целых числа, не превышающих по модулю 10^6 - x- и y-координаты очередной вершины. В следующей строке задано число Q - количество запросов от начальства (оно не ограничено явно, но гарантировано, что все запросы разные). Каждая из последующих Q строк содержит запрос в формате: сначала количество K (3 ≤ K ≤ N) вершин, через которые надо пройти, потом номера этих вершин (каждый номер в пределах от 1 до N, все вершины в одном запросе разные.

Выходные данные

Программа должна вывести Q строк, в каждой из которых - единственное действительное число, равное ответу на соответствующий запрос. Ответ вывести с точностью 2 знака после десятичной точки.

Пример

Входные данные #1
4
0 0
10 0
0 10
10 10
2
4 1 2 3 4
3 1 2 4
Выходные данные #1
40.00
34.14