Problem1033--安全区域

1033: 安全区域

[Creator : ]
Time Limit : 3.000 sec  Memory Limit : 128 MB

Submit

Description

太空中有n 类卫星(即类型1、类型2…)共m个。对于满足1<=i<=n的任意整数i,类型i的所有卫星共同保卫着包含它们的最小凸多面体(即凸包。可能会退化,即体积为0)。如果空间中一个点被至少k 类卫星保护,我们说这个点属于安全区域。

你的任务是计算所有安全区域的总体积。

Input

输入第一行为数据组数T (T<=25)。每组数据第一行为三个整数n, km(1<=k<=n<=5, 4<=m<=50)。以下m 行每行包含三个实数x, yz,表示一个类型t 的卫星,坐标为(x,y,z)(1<=t<=n, 0<=x,y,z<=10)。每组输入数据后有一个空行。

Output

对于每组数据,输出安全区域的总体积,四舍五入保留小数点5位。

Sample Input Copy

2
2 1 16
1 0 0 0
1 0 0 2
1 0 2 0
1 0 2 2
1 2 0 0
1 2 0 2
1 2 2 0
1 2 2 2
2 1 1 1
2 1 1 3
2 1 3 1
2 1 3 3
2 3 1 1
2 3 1 3
2 3 3 1
2 3 3 3

1 1 4
1 0 0 0
1 0 1 0
1 0 0 1
1 1 0 0

Sample Output Copy

15.00000
0.16667

HINT

评测数据(而非样例数据)中卫星坐标都是随机生成的。