[AtCoder] ABC 145 C – Average Length
問題
方針
順列を生成して距離を計算します。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int a[8]; bool flag[8]; double ans = 0; double m; double x[8], y[8]; int N; int fact(int n) { if (n == 1) return 1; return n * fact(n - 1); } double norm(double x1, double y1, double x2, double y2) { return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); } void perm(int n) { if (n == N) { for (int i = 0; i < N - 1; i++) { ans += norm(x[a[i]], y[a[i]], x[a[i + 1]], y[a[i + 1]]) / m; } return; } for (int i = 0; i < N; i++) { if (flag[i]) continue; a[n] = i; flag[i] = true; perm(n + 1); flag[i] = false; } } int main() { cin >> N; for (int i = 0; i < N; i++) { cin >> x[i] >> y[i]; flag[i] = false; } m = fact(N); perm(0); printf("%0.9f\n", ans); return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません