{"problem":{"name":"Average Length","description":{"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}$. Ther","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc145_c"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$x_1$ $y_1$\n$:$\n$x_N$ $y_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc145_c","tags":[],"sample_group":[["3\n0 0\n1 0\n0 1","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...$"],["2\n-879 981\n-866 890","91.9238815543\n\nThere are two paths to visit the towns: $1$ → $2$ and $2$ → $1$. These paths have the same length."],["8\n-406 10\n512 859\n494 362\n-955 -475\n128 553\n-986 -885\n763 77\n449 310","7641.9817824387"]],"created_at":"2026-03-03 11:01:14"}}