Path Through Vertices#807
On a coordinate plane, you are given vertices. You are required to repeatedly find the shortest path that visits all specified vertices and returns to the starting point.
The length of the path is the sum of the lengths of its segments. The length of a segment between two points is calculated by the formula:
Why must the path be found multiple times? Because it is undecided which of the vertices are essential. Therefore, you must process different queries that specify different subsets of required vertices. The order in which the vertices are visited and the choice of the starting (and ending) point is up to the person searching for the minimal path, not predetermined.
The first line contains the number of vertices (4 \leq N \leq 17). Each of the next lines contains two integers, the and coordinates of a vertex (each coordinate does not exceed 10^6 by absolute value). The following line contains the number of queries (there is no explicit limit on , but all queries are distinct). Each of the next lines contains a query: first, the number (3 \leq K \leq N) of vertices to visit, followed by the indices of these vertices (each index is from to , and all vertices in a query are distinct).
The program should output lines, each containing a single real number that is the answer to the corresponding query. Output the answer to decimal places.
Example 1