Welcome to ZOJ Problem Sets Information Select Problem Runs Ranklist ZOJ Problem Set - 3989
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

Author: LIN, Xi
Source: The 2017 China Collegiate Programming Contest, Qinhuangdao Site
Submit    Status