#P18194. Triangulation

Triangulation

Triangulation

题目描述

给定平面上的点集 P,共有 n 个点,编号为 1 到 n。连接点 u 和点 v、画出一条线段的费用是 w[u,v]。

你需要选择一些点对并画出相应线段,使这些线段形成点集 P 的一个三角剖分。求最小总费用,以及达到最小费用的不同三角剖分数量。

这里,三角剖分是一个三角形集合,满足:

  1. 所有三角形的并集恰好等于 P 的凸包;
  2. 这些三角形的所有顶点组成的集合恰好是 P,不能忽略任何内部点;
  3. 任意两个不同三角形的交集,只能为空、一个公共顶点,或者一条完整的公共边。

费用按画出的不同线段计算,每条线段只计一次;两个三角形共用的边不能重复收费。凸包边也是必须画出的线段,也要计入总费用。计数区分的是不同三角剖分,不区分画线或枚举三角形的顺序。

下面是同一个九点集合的两种不同三角剖分。

同一点集的两种三角剖分,原题示意图

输入格式

第一行包含正整数 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,有两种选择。第二组有一个内部点,必须画出六条边,只有一种三角剖分。