Doubtful Management
On a coordinate plane, you are given N vertices, and the task is to repeatedly determine the shortest path that visits these vertices and returns to the starting point.
The path's length is the sum of its segments' lengths, with each segment's length calculated using the formula
Why calculate the path multiple times? It's because the management is undecided about which of the N vertices are necessary. Therefore, for the same set of vertices, you need to handle different queries, each specifying a different subset of required vertices. The order of visiting these vertices and the choice of starting (and ending) point is left to the one optimizing for the shortest path.
Input Data
The first line provides the number of vertices N (4 ≤ N ≤ 17). Each of the next N lines contains two integers, representing the x and y coordinates of a vertex, with values not exceeding 10^6 in absolute magnitude. The subsequent line indicates the number Q of queries from the management (there is no explicit limit on Q, but all queries are distinct). Each of the following Q lines describes a query: first, the number K (3 ≤ K ≤ N) of vertices to visit, followed by the indices of these vertices (each index ranges from 1 to N, and all vertices in a query are unique).
Output Data
The program should produce Q lines, each containing a single real number, which is the solution to the corresponding query. The result should be formatted to two decimal places.