Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
149 - The 2017 China Collegiate Programming Contest, Qinhuangdao Site - I
Triangulation

Time Limit: 2 Seconds      Memory Limit: 262144 KB

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

  • \(\text{conv}(P) = \bigcup\limits_{T \in \mathcal{T}}T\), where \(\text{conv}(P)\) is the convex hull of \(P\).
  • \(P = \bigcup\limits_{T \in \mathcal{T}}V(T)\), where \(V(T)\) is the set of three vertices of triangle \(T\).
  • For every distinct pair \(T, U \in \mathcal{T}\), \(T \cap U\) is either a common vertex, or a common edge, or empty.

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)

Input

There 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.

Output

For each test case, output two integers denoting the minimum cost and the number of triangulations.

Sample Input

2
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 Output

5 2
6 1

Submit    Status