← 返回题目列表

AtCoder · kupc2018_l

L. 凸包投影的平面

中文机器翻译题面 查看原题

配点 : 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