C - Average LengthD - 发呆

C - Average Length

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 300300 points

Problem Statement

There are NN towns in a coordinate plane. Town ii is located at coordinates (x_ixi, y_iyi). The distance between Town ii and Town jj is \sqrt{\left(x_i-x_j\right)^2 \left(y_i-y_j\right)^2}(xi−xj)2 (yi−yj)2.

There are N!N! possible paths to visit all of these towns once. Let the length of a path be the distance covered when we start at the first town in the path, visit the second, third, \dots…, towns, and arrive at the last town (assume that we travel in a straight line from a town to another). Compute the average length of these N!N! paths.

Constraints

• 2 \leq N \leq 82≤N≤8
• -1000 \leq x_i \leq 1000−1000≤xi≤1000
• -1000 \leq y_i \leq 1000−1000≤yi≤1000
• \left(x_i, y_i\right) \neq \left(x_j, y_j\right)(xi,yi)=(xj,yj) (if i \neq ji=j)
• (Added 21:12 JST) All values in input are integers.

---

Input

Input is given from Standard Input in the following format:

NN
x_1x1 y_1y1
::
x_NxN y_NyN

Output

Print the average length of the paths. Your output will be judges as correct when the absolute difference from the judge's output is at most 10^{-6}10−6.

---

Sample Input 1 Copy

Copy

3
0 0
1 0
0 1

Sample Output 1 Copy

Copy

2.2761423749

There are six paths to visit the towns: 11 → 22 → 33, 11 → 33 → 22, 22 → 11 → 33, 22 → 33 → 11, 33 → 11 → 22, and 33 → 22 → 11.

The length of the path 11 → 22 → 33 is \sqrt{\left(0-1\right)^2 \left(0-0\right)^2} \sqrt{\left(1-0\right)^2 \left(0-1\right)^2} = 1 \sqrt{2}(0−1)2 (0−0)2 (1−0)2 (0−1)2=1 2.

By calculating the lengths of the other paths in this way, we see that the average length of all routes is:

\frac{\left(1 \sqrt{2}\right) \left(1 \sqrt{2}\right) \left(2\right) \left(1 \sqrt{2}\right) \left(2\right) \left(1 \sqrt{2}\right)}{6} = 2.276142...6(1 2) (1 2) (2) (1 2) (2) (1 2)=2.276142...

---

Sample Input 2 Copy

Copy

2
-879 981
-866 890

Sample Output 2 Copy

Copy

91.9238815543

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

---

Sample Input 3 Copy

Copy

8
-406 10
512 859
494 362
-955 -475
128 553
-986 -885
763 77
449 310

Sample Output 3 Copy

Copy

7641.9817824387

 题意：

平面上给你n个点，并告诉你它们的坐标，现在你要画一笔画，用n-1条折线把这n个点连起来，这样有n!种不同的画法。现在想求出这些画法所画出来的路线的平均长度

 在这里提醒一下想把累和写进递归途中去省掉一个循环的py们，这个基本不可能实现，全排列时每次会选定一个节点，而累加值会从节点处开始，这样会少加前面的长度，而前面的长度又在1~（n-1）！中变化，虽然有规律，但是需要一个较大的数组暂存每种情况下每个节点之前的值，再随规律调动，而规律是波动的（随着初始节点），这个大家手动模拟一个n=4的全排列就知道了，所以该方法看似少了一个循环，实则将整个程序的空间，时间复杂度都提升了不少，再者，求累和的小循环循环节连10都不到，根本不会浪费时间，所以老老实实用普通的方法写吧，别想某人一样（指我）浪费快一天.....

1.  
   #define _CRT_SECURE_NO_WARNINGS
2.  
   #include<iostream>
3.  
   #include<algorithm>
4.  
   #include<cstring>
5.  
   #include<cmath>
6.  
   #include<iomanip>
7.  
   using namespace std;
8.  
   typedef long long ll;
9.  
   int k[10][3], lowk[10][3], n, t;
10.  
    bool p[10];
11.  
    double sum, lowsum;
12.  
    double length(int x1, int y1, int x2, int y2) {
13.  
    return sqrt((double)((x1 - x2) * (x1 - x2) (y1 - y2) * (y1 - y2)));
14.  
    }
15.  
    void dfs(int m) {
16.  
    if (m == n) {
17.  
    t ;//顺便求一共有几种排序
18.  
    for (int i = 1; i < n; i ) {
19.  
    sum = length(lowk[i - 1][0], lowk[i - 1][1], lowk[i][0], lowk[i][1]);//求当前排序的和
20.  
    }
21.  
    return;
22.  
    }
23.  
    for (int i = 1; i <= n; i ) {
24.  
    if (!p[i]) {
25.  
    p[i] = true;
26.  
    lowk[m][0] = k[i][0], lowk[m][1] = k[i][1];//按顺序储存点
27.  
    dfs(m 1);
28.  
    p[i] = false;
29.  
    }
30.  
    }
31.  
    }
32.  
    int main() {
33.  
    ios::sync_with_stdio(false);
34.  
    cin.tie(0);
35.  
    cin >> n;
36.  
    for (int i = 1; i <= n; i ) {
37.  
    cin >> k[i][0] >> k[i][1];
38.  
    }
39.  
    dfs(0);
40.  
    printf("%.10lf", sum/t);
41.  
    return 0;
42.  
    }

这篇好文章是转载于：学新通技术网