{"raw_statement":[{"iden":"problem statement","content":"There are $N$ towns in a coordinate plane. Town $i$ is located at coordinates ($x_i$, $y_i$). The distance between Town $i$ and Town $j$ is $\\sqrt{\\left(x_i-x_j\\right)^2+\\left(y_i-y_j\\right)^2}$.\nThere are $N!$ possible paths to visit all of these towns once. Let the length of a path be the distance covered when we start at the first town in the path, visit the second, third, $\\dots$, towns, and arrive at the last town (assume that we travel in a straight line from a town to another). Compute the average length of these $N!$ paths."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 8$\n*   $-1000 \\leq x_i \\leq 1000$\n*   $-1000 \\leq y_i \\leq 1000$\n*   $\\left(x_i, y_i\\right) \\neq \\left(x_j, y_j\\right)$ (if $i \\neq j$)\n*   (Added 21:12 JST) All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$x_1$ $y_1$\n$:$\n$x_N$ $y_N$"},{"iden":"sample input 1","content":"3\n0 0\n1 0\n0 1"},{"iden":"sample output 1","content":"2.2761423749\n\nThere are six paths to visit the towns: $1$ → $2$ → $3$, $1$ → $3$ → $2$, $2$ → $1$ → $3$, $2$ → $3$ → $1$, $3$ → $1$ → $2$, and $3$ → $2$ → $1$.\nThe length of the path $1$ → $2$ → $3$ is $\\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}$.\nBy calculating the lengths of the other paths in this way, we see that the average length of all routes is:\n$\\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...$"},{"iden":"sample input 2","content":"2\n-879 981\n-866 890"},{"iden":"sample output 2","content":"91.9238815543\n\nThere are two paths to visit the towns: $1$ → $2$ and $2$ → $1$. These paths have the same length."},{"iden":"sample input 3","content":"8\n-406 10\n512 859\n494 362\n-955 -475\n128 553\n-986 -885\n763 77\n449 310"},{"iden":"sample output 3","content":"7641.9817824387"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}