下面是题目复述：

Sample Input 1

3

0 0

1 0

0 1

Sample Output 1

2.2761423749

There are six paths to visit the towns: 1 → 2 → 3, 1 → 3 → 2, 2 → 1 → 3, 2 → 3 → 1, 3 → 1 → 2, and 3 → 2 → 1.

Sample Input 2

2

-879 981

-866 890

Sample Output 2

91.9238815543

There are two paths to visit the towns: 1 → 2 and 2 → 1. These paths have the same length.

Sample Input 3

8

-406 10

512 859

494 362

-955 -475

128 553

-986 -885

763 77

449 310

Sample Output 3

7641.9817824387

下面是解题过程：

本来以为要用结构体或者什么规律数学知识之类的……仔细一看，n的范围2~8，直接开始暴搜。

1. 判断要一个点一个点的搜索，所有点都会被用到，所有点都有做排头的机会，然后递归求出每个点做排头的几种情况。
2. 然后把情况数和距离数分别统计出来，相除即可。
3. 特别的，在dfs回溯的时候，记得把之前用过的bool变量和长度恢复原样。

PS：注意精度和每个变量代表的含义，不要变量指代错误。

下面是AC代码：

#include <iostream>
#include <cstdio>
#include <cmath>
const int N=10;
using namespace std;
double sum=0,tmp,snum=0;
typedef pair<double,double> PII;
bool flag[N];

PII a[N];
int n;
void dfs(int x,int num)//num代表位数，x代表数字
{
    if(num==n-1)
    {
        sum+=tmp;
        snum++;
        return ;
    }

    for(int i=0; i<n; i++)
    {
        if(!flag[i])
        {
            double dist=sqrt(pow(a[x].first-a[i].first,2)+pow(fabs(a[x].second-a[i].second),2));//求距离
            flag[i]=true;
            tmp+=dist;
            dfs(i,num+1);
            tmp-=dist;//恢复原样
            flag[i]=false;

        }
    }

}
int main()
{
    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        scanf("%lf%lf",&a[i].first,&a[i].second);
    }
    for(int i=0; i<n; i++)
    {
        flag[i]=true;
        dfs(i,0);
        flag[i]=false;
    }
    printf("%.10f\n",sum/snum);
    return 0;
}