Шлях через вершини#807
На координатній площині вам задано вершин. Вам потрібно багаторазово знаходити найкоротший шлях, який проходить через усі зазначені вершини і повертається в початкову точку.
Довжина шляху — це сума довжин його відрізків. Довжину відрізка між двома точками обчислюють за формулою:
Чому шлях треба знаходити кілька разів? Тому що не визначено, які саме з вершин є обов'язковими. Тож потрібно обробити різні запити, які визначають різні підмножини необхідних вершин. Порядок відвідування вершин, а також вибір початкової (і кінцевої) точки повністю залежить від того, хто шукає мінімальний шлях, і не є наперед заданими.
У першому рядку міститься число вершин (4 \leq N \leq 17). Кожен з наступних рядків містить по два цілі числа — координати та вершини (кожна координата за абсолютним значенням не перевищує 10^6). Далі в одному рядку записане число запитів (явної межі на немає, але всі запити різні). Кожен із наступних рядків містить опис запиту: спочатку число (3 \leq K \leq N) — кількість вершин, які треба відвідати, а потім індекси цих вершин (кожен індекс від до , усі вершини в одному запиті різні).
Програма повинна вивести рядків, у кожному з яких одне дійсне число — відповідь на відповідний запит. Відповідь виводьте з точністю до знаків після коми.
Приклад 1