Kyoto University Programming Contest 2018

L - 凸包が映し出される平面


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 1024MB

配点 : 500

問題文

3 次元空間上に N 個の点があり、i 番目の点の座標は (x_i, y_i, z_i) です。

まず、あなたは長さが 13 次元ベクトル 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

Submit提出する