問題

問題概要

座標平面上に N個の町があります。町iは座標(xi ,yi) に位置しています。町iと町jの間の距離は√(xi−xj)2 +(yi−yj)2です。
これらの町を全て 1回ずつ訪れるとき、町を訪れる経路は全部でN!通りあります。1番目に訪れる町から出発し、2番目に訪れる町、3番目に訪れる町、…を経由し、N
番目に訪れる町に到着するまでの移動距離(町から町への移動は直線移動とします)を、その経路の長さとします。これらのN!通りの経路の長さの平均値を計算してください。

制約

• $2≤N≤8$
• $−1000≤xi≤1000$
• $−1000≤yi≤1000$
• $(xi,yi)≠(xj,yj)(i≠j のとき)$
• 入力中の値はすべて整数である。

考えたこと

町を訪れる経路1,からNの数字の組み合わせを全通り試せばよい
Ex:Nが3のとき
1 → 2 → 3 , 1 → 3 → 2 , 2 → 1 → 3 , 2 → 3 → 1 , 3 → 1 → 2 , 3 → 2 → 1 の 6通り。
これは、(1 , 2 , 3)の順列全通りです。
これにはnext_permutation()を使いました。

next_permutation()とは

与えられた時点の[first, last)の範囲を起点の順列として、辞書順によるその次の順列を生成する。
引用元

#includeすることで使えます。

例えばvector = {1,2,3}を与えると辞書順で

{1,2,3}

{1,3,2}

{2,1,3}

を返します。

コード

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;

int facctorialMethod(int k)
{
  int sum = 1;
  for (int i = 1; i <= k; ++i)
  {
    sum *= i;
  }
  return sum;
}

int main()
{
  int N;
  cin >> N;
  vector<int> x(N), y(N);
  vector<int> P(N);
  rep(i, N)
  {
    cin >> x[i] >> y[i];
    P[i] = i;
  }
  double ans;
  do
  {
    rep(i, N - 1)
    {
      ans += pow(pow((x[P[i]] - x[P[i + 1]]), 2) + pow((y[P[i]] - y[P[i + 1]]), 2), (1.0 / 2.0));
    }
  } while (next_permutation(P.begin(), P.end()));

  printf("%.12lf",ans / facctorialMethod(N));
}