#abc145c. [abc145_c]Average Length

[abc145_c]Average Length

問題文

座標平面上に NN 個の町があります。町 ii は、座標 ( xix_i , yiy_i ) に位置しています。町 ii と町 jj の間の距離は sqrtleft(xixjright)2+left(yiyjright)2\\sqrt{\\left(x_i-x_j\\right)^2+\\left(y_i-y_j\\right)^2} です。

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

制約

  • 2N82 ≤ N ≤ 8
  • \-1000xi1000\-1000 ≤ x_i ≤ 1000
  • \-1000yi1000\-1000 ≤ y_i ≤ 1000
  • left(xi,yiright)neqleft(xj,yjright)\\left(x_i, y_i\\right) \\neq \\left(x_j, y_j\\right) ( ineqji \\neq j のとき)
  • (21:12 追記) 入力中の値はすべて整数である。

入力

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

NN x1x_1 y1y_1 :: xNx_N yNy_N

出力

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


入力例 1

3
0 0
1 0
0 1

出力例 1

2.2761423749

町を訪れる経路は 112233 , 113322 , 221133 , 223311 , 331122 , 33221166 通りです。

このうち、経路 112233 の長さは、sqrtleft(01right)2+left(00right)2+sqrtleft(10right)2+left(01right)2=1+sqrt2\\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} となります。

同様に他の経路についても長さを計算すると、経路の長さの平均値は、

fracleft(1+sqrt2right)+left(1+sqrt2right)+left(2right)+left(1+sqrt2right)+left(2right)+left(1+sqrt2right)6=2.276142...\\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...

であると分かります。


入力例 2

2
-879 981
-866 890

出力例 2

91.9238815543

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


入力例 3

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

出力例 3

7641.9817824387