#P1209. [HNOI2004]最佳包裹

    ID: 217 传统题 1000ms 512MiB 尝试: 315 已通过: 88 难度: 7 上传者: 标签>CF2200提高三维凸包组合枚举混合积判断共面投影Andrew 算法鞋带公式有序集合

[HNOI2004]最佳包裹

[HNOI2004] 最佳包裹

题目描述

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

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

输入格式

输入文件由若干行组成:第1行是一个整数n(4≤n≤1004 \leq n \leq 100),表示顶点的个数;第 22 行到第 n+1n+1 行,每行是 33 个实数 xi,yi,zix_i,y_i,z_i,表示第 ii 个顶点的坐标。每个顶点的位置各不相同。

输出格式

输出文件只有一个实数,表示包裹一个该产品所需的材料面积的最小值。

样例 #1

样例输入 #1

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

样例输出 #1

2.366025

本站当前数据版本的数值范围

本站当前安装的10组原数据已逐个坐标扫描,坐标绝对值不超过102,小数部分不超过2位。当前教学版本采用该数值范围,输入十进制数可精确乘100化为整数。组合几何判定应在该整数坐标上精确进行,最后才计算欧氏面积并四舍五入到6位,不能用固定EPS删掉合法小体积结构。此限制来源于本站原测试数据核验,不冒称原HNOI题面已有保证。