配点 : 500 点
問題文
3 论维度空间 有 N 点, 第i 点的坐标是 (x_i, y_i, z_i) 。
首先,你需要知道长度是 1 的 可以考虑 3 维向量 自由选择 v 。
接下来,经过原点 垂直于 v 的平面 垂直于 F 。
各 (x_i, y_i, z_i) 它们的编号最大为 F 的脚 p_i 。
平面 F 顶点打开 创建 p_1, p_2, ..., p_N 的凸包并求其面积 找到 S 。
面積 S 的最大值,然后 最大化S 的向量 有多少种方式选择 v ? 除以 10^9 + 7 并求余数。
制約
- 输入全部为整数。
- 4 \leq N \leq 60
- 0 \leq x_i, y_i, z_i \leq 1,000
- 给定点的坐标都不同。
- 所有点都不位于同一平面上。
- 使得面积最大 最多有有限种选择方法 v 。 打印
入力
输入是按以下格式从标准输入给出的。
N x_1 y_1 z_1 x_2 y_2 z_2 : x_N y_N z_N
出力
面積 S 的最大值。
接下来, 除以S 的向量 有多少种方式选择 v ? 除以 10^9 + 7 并打印余数。
此外,该地区 对于 S 的最大值,绝对或相对误差为 如果小于 10^{−8} ,则视为正确。
入力例 1
4 0 0 0 1 0 0 0 1 0 0 0 1
出力例 1
0.866025403784 2
v = (1 / \sqrt{3}, 1 / \sqrt{3}, 1 / \sqrt{3}) 然后从每个顶点 垂直于 F 的脚的凸包是一侧 就变成了 \sqrt{2} 的等边三角形,此时的面积为 \sqrt{3} / 2 是最大值。 同样,当
v = (-1 / \sqrt{3}, -1 / \sqrt{3}, -1 / \sqrt{3}) 同样,当F 上面凸包的面积是 \sqrt{3} / 2 。
该区域将 如何选择 v 如何选择 2 仅限街道。
入力例 2
4 0 0 0 0 1 1 1 0 1 1 1 0
出力例 2
1.000000000000 6
入力例 3
8 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
出力例 3
1.732050807569 8
入力例 4
27 0 0 0 0 0 1 0 0 2 0 1 0 0 1 1 0 1 2 0 2 0 0 2 1 0 2 2 1 0 0 1 0 1 1 0 2 1 1 0 1 1 1 1 1 2 1 2 0 1 2 1 1 2 2 2 0 0 2 0 1 2 0 2 2 1 0 2 1 1 2 1 2 2 2 0 2 2 1 2 2 2
出力例 4
6.928203230276 8
入力例 5
24 2 3 4 2 4 3 3 2 4 3 4 2 4 2 3 4 3 2 2 1 4 2 4 1 1 2 4 1 4 2 4 2 1 4 1 2 2 3 0 2 0 3 3 2 0 3 0 2 0 2 3 0 3 2 2 1 0 2 0 1 1 2 0 1 0 2 0 2 1 0 1 2
出力例 5
14.282856857086 24