
ZOJ Problem Set  3989
DreamGrid has a point set \(P\) of \(n\) points. The points are labeled from \(1\) to \(n\). He would like to draw some segments between some pairs of points such that the final result forms a triangulation. The cost for drawing segment between points \(u\) and \(v\) is \(w_{u,v}\). DreamGrid would like to know the minimum total cost and the number of triangulations which can achieve the minimum total cost. A triangulation of a point set \(P\) is a collection \(\mathcal{T}\) of triangles, such that
For example, the following are two different triangulations of the same set of 9 points. (From Wikipedia. https://en.wikipedia.org/wiki/Point_set_triangulation) InputThere are multiple test cases. The first line of input contains an integer \(T\) (about 70), indicating the number of test cases. For each test case: The first line contains an integer \(n\) \((3 \le n \le 18)\)  the number of points. Each of the next \(n\) lines contains two integers \(x_i\) and \(y_i\) \((0 \le x_i, y_i \le 10^6)\), denoting the coordinates of the \(i\)th point. No three points lie on the same line. The \(i\)th of the next \(n\) lines contains \(n\) integers \(w_{i,1}, w_{i,2}, \dots, w_{i,n}\) (\(0 \le w_{i, j} \le 10^6, w_{i,i}=0, w_{i,j}=w_{j,i}\)), indicating the cost for drawing segments. OutputFor each test case, output two integers denoting the minimum cost and the number of triangulations. Sample Input2 4 0 0 1 1 1 0 0 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 4 0 0 3 0 1 3 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 Sample Output5 2 6 1 Author: LIN, Xi Source: The 2017 China Collegiate Programming Contest, Qinhuangdao Site 