実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 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