AT5226 [ABC145C] Average Length 题解

题意简述

给定一个整数 $n$，代表有 $n$ 个点。

给出 $n$ 对数，每一对数有两个数 $x_i,y_i$ 组成，代表每个点的坐标。

任意两个点之间都有路径，路径等于两点之间的欧几里得距离。

问求 $n!$ 条边遍历所有点各一遍的路径总长度的平均值。

题目翻译中没写到的是，最终输出保留 $10$ 位小数。

解题思路

首先，我们知道欧几里得距离的求法如下：

$dis_{i \to j} = \sqrt{(x_i - x_j)^2 + (y_i-y_j)^2}$

在第 $i$ 次输入时，我们要记录下 $x_i,y_i$，然后 $1 \to (i-1)$ 遍历一遍，在第 $j$ 个点上，让 $ans$ 累加上 $dis_{i \to j}$。

因为题目要的是平均距离，所以输出 $\dfrac{ans}{n}$？

不是，应该要输出 $\dfrac{2 \times ans}{n}$。

因为题目要求的是 $n!$ 条边，每个点之间有 $\dfrac{[1+(n-1)] \times (n-1)}{2}$，化简得 $\dfrac{n^2-n}{2}$，这样平均到每条边上有 $\dfrac{n^2-n}{2} \times n!$，化简得 $(n-1)! \times 2$。

所以最终输出 $\dfrac{2 \times ans}{n}$ 即可。

代码实现

#include<bits/stdc++.h>
using namespace std;
int n; double x[10005],y[10005],ans;
double dis(double x1,double x2,double y1,double y2) {
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%lf%lf",&x[i],&y[i]);
		for(int j=1;j<i;j++) ans+=dis(x[i],x[j],y[i],y[j]);
	}
	printf("%.10lf",ans*2/n);
	return 0;
}
//code by _IcyFire