#P18194. Triangulation
Triangulation
Triangulation
题目描述
给定平面上的点集 P,共有 n 个点,编号为 1 到 n。连接点 u 和点 v、画出一条线段的费用是 w[u,v]。
你需要选择一些点对并画出相应线段,使这些线段形成点集 P 的一个三角剖分。求最小总费用,以及达到最小费用的不同三角剖分数量。
这里,三角剖分是一个三角形集合,满足:
- 所有三角形的并集恰好等于 P 的凸包;
- 这些三角形的所有顶点组成的集合恰好是 P,不能忽略任何内部点;
- 任意两个不同三角形的交集,只能为空、一个公共顶点,或者一条完整的公共边。
费用按画出的不同线段计算,每条线段只计一次;两个三角形共用的边不能重复收费。凸包边也是必须画出的线段,也要计入总费用。计数区分的是不同三角剖分,不区分画线或枚举三角形的顺序。
下面是同一个九点集合的两种不同三角剖分。

输入格式
第一行包含正整数 T,表示测试组数。原题的描述为约 70 组。
对于每组数据:
- 第一行包含整数 n;
- 接下来 n 行,每行包含两个整数 x[i],y[i],表示第 i 个点的坐标;
- 接下来 n 行,第 i 行包含 n 个整数 w[i,1],w[i,2],...,w[i,n],表示连接各点对的费用。
输出格式
对于每组数据,输出两个整数:最小总费用、达到该费用的三角剖分数量。
计数必须精确输出,不取模。
数据范围
- 3<=n<=18;
- 0<=x[i],y[i]<=1000000;
- 所有点互不相同,任意三个点不共线;
- 0<=w[i,j]<=1000000;
- w[i,i]=0,w[i,j]=w[j,i]。
点集不保证处于凸位置,可能含有位于凸包内部的点。原题没有另给所有测试的 n 之和等限制。
样例
输入:
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
输出:
5 2
6 1
第一组是凸四边形:四条凸包边和一条对角线,总费用为 5,有两种选择。第二组有一个内部点,必须画出六条边,只有一种三角剖分。