题目描述

座標平面上に $N$ 個の町があります。町 $i$ は、座標 ( $x_i$ , $y_i$ ) に位置しています。町 $i$ と町 $j$ の間の距離は $ \sqrt{\left(x_i-x_j\right)^2+\left(y_i-y_j\right)^2} $ です。

これらの町を全て $1$ 回ずつ訪れるとき、町を訪れる経路は全部で $N!$ 通りあります。$1$ 番目に訪れる町から出発し、$2$ 番目に訪れる町、$3$ 番目に訪れる町、$\ldots$、を経由し、$N$ 番目に訪れる町に到着するまでの移動距離 (町から町への移動は直線移動とします) を、その経路の長さとします。これらの $N!$ 通りの経路の長さの平均値を計算してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $x_1$ $y_1$ $:$ $x_N$ $y_N$

输出格式

経路の長さの平均値を出力せよ。 出力は、ジャッジの出力との絶対誤差または相対誤差が $10^{-6}$ 以下のとき正解と判定される。

题目大意

有 n 个点，每两个点之间都有路径，路径长度为它们的欧几里得距离。

求 n! 条遍历所有点各一遍的路径总长度的平均值。

3
0 0
1 0
0 1

2.2761423749

2
-879 981
-866 890

91.9238815543

8
-406 10
512 859
494 362
-955 -475
128 553
-986 -885
763 77
449 310

7641.9817824387

提示

制約

• $2\ <\ =\ N\ <\ =\ 8$
• $-1000\ <\ =\ x_i\ <\ =\ 1000$
• $-1000\ <\ =\ y_i\ <\ =\ 1000$
• $ \left(x_i,\ y_i\right)\ \neq\ \left(x_j,\ y_j\right) $ ( $i\ \neq\ j$ のとき)
• (21:12 追記) 入力中の値はすべて整数である。

Sample Explanation 1

町を訪れる経路は $1$ → $2$ → $3$ , $1$ → $3$ → $2$ , $2$ → $1$ → $3$ , $2$ → $3$ → $1$ , $3$ → $1$ → $2$ , $3$ → $2$ → $1$ の $6$ 通りです。 このうち、経路 $1$ → $2$ → $3$ の長さは、$ \sqrt{\left(0-1\right)^2+\left(0-0\right)^2}\ +\ \sqrt{\left(1-0\right)^2+\left(0-1\right)^2}\ =\ 1+\sqrt{2} $ となります。 同様に他の経路についても長さを計算すると、経路の長さの平均値は、 $ \frac{\left(1+\sqrt{2}\right)+\left(1+\sqrt{2}\right)+\left(2\right)+\left(1+\sqrt{2}\right)+\left(2\right)+\left(1+\sqrt{2}\right)}{6}\ =\ 2.276142... $ であると分かります。

Sample Explanation 2

町を訪れる経路は $1$ → $2$ , $2$ → $1$ の $2$ 通りありますが、これらの経路の長さは一致します。