The Cyber Traveling Salesman
In light of the exploding population on earth, a number of cities are being constructed on the moon. We would like you to assist in determining the best road system for these cities. Considering the high cost associated with building roads on the moon, all what is required is for the roads to form a cycle starting from the city that appears first in the input, passing through all other cities exactly once (but in any arbitrary order,) and then ending back to the first. (Yes, this problem is a variation of the traveling-salesman problem.)
You are given the cost of building a road between each pair of cities. Roads are one-way, but the cost for building a road from city i to j is the same as the cost of building from city j to i. When roads intersect at a location that is not a city, you must account for the cost of constructing bypassing bridges. Constructing a bypass system costs k·(k-1)·C/2 where k is the number of roads intersecting at that location, and C is a given constant.
Note that the cities are laid out so that no three cities fall on the same straight line.
Input
Your program will be tested on one or more test cases. Each test case is specified using 2·N+1 lines. The first line specifies two integers: (2 < N < 9) is the number of cities and (0 < C ≤ 1000000) is the coefficient used in determining the cost of building bridges.
Following the first line, the Cartesian coordinates of the cities are specified in order. Each city is specified on a separate line made of two integers: x_i and y_i where (-1000 ≤ x_i, y_i ≤ 1000). No two cities are located at the same (x, y) location.
The last N lines of a test case specify an N×N matrix representing the cost of building a road between any two cities. The matrix is specified using N lines, each with N integers in a row-major format. The j^th value on the i^th row, denoted as c_ij is the cost of building a road from city-i to city-j where (0 < c_ij ≤ 10^6) and (c_ij = c_ji) and (c_ii = 0).
The last case is followed by a line having two zeros.
Output
For each test case, print the following line:
k. M
Where k is the test case number (starting at one,) and M is minimum cost needed to build the road system.
