Average Length [AtCoder Beginner Contest 145 C]

https://atcoder.jp/contests/abc145/tasks/abc145_c

解説

https://atcoder.jp/contests/abc145/submissions/8483703

まず、Nが非常に小さい。
経路は全部でN!通りあるが、最大でも40320通りなので、これは全探索ができる。
C++だとnext_permutationを使うと実現可能だ。

あとは、全部の経路について移動距離を計算し、その総和÷N!とすれば答え。

int N, X[8], Y[8];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> X[i] >> Y[i];

    vector<int> ord;
    rep(i, 0, N) ord.push_back(i);

    long double sm = 0;
    do {
        rep(i, 0, N - 1) {
            int a = ord[i];
            int b = ord[i + 1];

            long double dx = X[a] - X[b];
            long double dy = Y[a] - Y[b];

            sm += sqrt(dx * dx + dy * dy);
        }
    } while (next_permutation(all(ord)));

    rep(i, 0, N) sm /= (i + 1);
    printf("%.10Lf\n", sm);
}