SP760 CH3D - Convex Hull 3D
题目描述
珂学家开发了一种全新的方法来测定一个人的肺的体积。这个想法很简单:病人被要求吸入足够多的纳米机器人,然后将其精确的3D坐标传送到外部传感器。这个想法很有趣,但是引起了一些算法上的问题。换句话说,没有人知道以后应该如何确定肺的体积。肺由大量不相交的肺泡组成(这些肺泡可以被看作是小空洞),吸入的纳米机器人往往会在它们碰巧落入的肺泡内漫无目的地漂浮。然而,区分不同的肺泡相对简单,而确定单个肺泡的体积则是一项艰巨的任务。
一种估计肺泡形状和体积的方法是用一点液体胶水涂抹所有的纳米机器人,看看它们最终粘在什么上面。另一种(可以说更人道的)方法是计算凸壳表示纳米机器人坐标的一组点,其体积和表面积。三维给定点集的凸包是包含所有这些点的最小体积凸集。
输入格式
第一行一个整数t为测试样例数目[t
输出格式
对于每个测试样例,您应该输出两个实数:船体的表面积和体积,精确到0.01,中间用空格隔开。