#P2287. [HNOI2004] 最佳包裹

    ID: 1239 远端评测题 1000ms 125MiB 尝试: 2 已通过: 2 难度: 6 上传者: 标签>各省省选湖南2004递推动态规划dp凸包

[HNOI2004] 最佳包裹

题目描述

发强公司生产了一种金属制品,是由一些笔直的金属条连接起来的,金属条和别的金属条在交点上被焊接在了一起。现在由于美观需要,在这个产品用一层特殊的材料包裹起来。公司为了节约成本,希望消耗的材料最少(不计裁剪时的边角料的损失)。

编程,输入包括该产品的顶点的个数,以及所有顶点的坐标;请计算出包裹这个产品所需要的材料的最小面积。结果要求精确到小数点后第六位(四舍五入)。

输入格式

输入文件由 (n+1)(n+1) 行组成。

11 行是一个整数 nn4n1004 \leq n \leq 100),表示顶点的个数;

22 行到第 (n+1)(n+1) 行,第 (i+1)(i+1) 行有 33 个实数 xix_iyiy_iziz_i,表示第 ii 个顶点的坐标。

保证顶点的位置各不相同。

输出格式

输出文件只有一个实数,四舍五入精确到小数点后六位,表示包裹一个该产品所需的材料面积的最小值。

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

2.366025