問題文
座標平面上に N 個の町があります。町 i は、座標 ( xi , yi ) に位置しています。町 i と町 j の間の距離は sqrtleft(xi−xjright)2+left(yi−yjright)2 です。
これらの町を全て 1 回ずつ訪れるとき、町を訪れる経路は全部で N! 通りあります。1 番目に訪れる町から出発し、2 番目に訪れる町、3 番目に訪れる町、ldots、を経由し、N 番目に訪れる町に到着するまでの移動距離 (町から町への移動は直線移動とします) を、その経路の長さとします。これらの N! 通りの経路の長さの平均値を計算してください。
制約
- 2≤N≤8
- \-1000≤xi≤1000
- \-1000≤yi≤1000
- left(xi,yiright)neqleft(xj,yjright) ( ineqj のとき)
- (21:12 追記) 入力中の値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
x1 y1
:
xN yN
出力
経路の長さの平均値を出力せよ。 出力は、ジャッジの出力との絶対誤差または相対誤差が 10−6 以下のとき正解と判定される。
入力例 1
出力例 1
町を訪れる経路は 1 → 2 → 3 , 1 → 3 → 2 , 2 → 1 → 3 , 2 → 3 → 1 , 3 → 1 → 2 , 3 → 2 → 1 の 6 通りです。
このうち、経路 1 → 2 → 3 の長さは、sqrtleft(0−1right)2+left(0−0right)2+sqrtleft(1−0right)2+left(0−1right)2=1+sqrt2 となります。
同様に他の経路についても長さを計算すると、経路の長さの平均値は、
fracleft(1+sqrt2right)+left(1+sqrt2right)+left(2right)+left(1+sqrt2right)+left(2right)+left(1+sqrt2right)6=2.276142...
であると分かります。
入力例 2
出力例 2
町を訪れる経路は 1 → 2 , 2 → 1 の 2 通りありますが、これらの経路の長さは一致します。
入力例 3
出力例 3