ABC 145 C - Average Length 順列全探索

C - Average Length

問題概要

平面上でN個の座標が与えられる。全ての点を１回ずつ通るような動き方はN!通りあるが、これらの総移動距離の平均を求めよ。

制約

2 ≤ N ≤ 8
−1000≤xi≤1000
−1000≤yi≤1000
( xi , yi ) ≠ ( xj , yj )

考えたこと

順列全探索の問題だということは分かっていた。next_permutationを使うことを視野に入れると、1~Nまでの順の配列を作って回すのが一番楽だと考えた。
今回の問題は特に苦労しなかった。

こーど

int N;

int main() {
	cin >> N;

	vector<int>DataN(N);
	for (int i = 0; i < N; i++) DataN[i] = i;

	vector<vector<int>> Machi(N, vector<int>(2));
	for (int i = 0; i < N; i++) {
		cin >> Machi[i][0];
		cin >> Machi[i][1];
	}

	double count = 0;
	double j = 0;
	do {
		for (int i = 0; i < N - 1; i++) {

			int numx = Machi[DataN[i]][0] - Machi[DataN[i + 1]][0];
			int numy = Machi[DataN[i]][1] - Machi[DataN[i + 1]][1];

			count += sqrt(pow(numx, 2) + pow(numy, 2));
		}
		j++;
	} while (next_permutation(DataN.begin(), DataN.end()));

	cout << fixed << setprecision(10) << count / j;
}