Welcome to ZOJ
 Contests 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