Có \(N\) thị trấn trên mặt phẳng tọa độ. Thị trấn \(i\) nằm tại tọa độ \((x_i, y_i)\). Khoảng cách giữa thị trấn \(i\) và thị trấn \(j\) là \(\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}\).

Có \(N!\) đường đi có thể để thăm tất cả các thị trấn một lần. Độ dài của một đường đi là khoảng cách được bao phủ khi chúng ta bắt đầu tại thị trấn đầu tiên trong đường đi, thăm thị trấn thứ hai, thứ ba, ..., và đến thị trấn cuối cùng (giả sử rằng chúng ta đi theo đường thẳng từ một thị trấn đến một thị trấn khác). Tính độ dài trung bình của các đường đi này.

Ràng buộc

\(2 \leq N \leq 8\)

\(−1000 \leq x_i \leq 1000\)

\(−1000 \leq y_i \leq 1000\)

\((x_i, y_i) \ne (x_j, y_j)\) (nếu \(i \ne j\))

(Tất cả các giá trị trong đầu vào là số nguyên.)

Định dạng nhập

Dữ liệu nhập được cung cấp từ đầu vào chuẩn theo định dạng sau:

\(N\)

\(x_1\) \(y_1\)

\(x_2\) \(y_2\)

...

\(x_N\) \(y_N\)

Định dạng xuất

In ra độ dài trung bình của các đường đi. Đầu ra của bạn sẽ được đánh giá là đúng nếu sự khác biệt tuyệt đối so với đầu ra của giám khảo không quá \(10^{-6}\).

Ví dụ:

Input

3
0 0
1 0
0 1

Output

2.2761423749

Có sáu đường đi để thăm các thị trấn: \(1 \to 2 \to 3, 1 \to 3 \to 2, 2 \to 1 \to 3, 2 \to 3 \to 1, 3 \to 1 \to 2, và 3 \to 2 \to 1\).

Độ dài của đường đi \(1 \to 2 \to 3\) là \(\sqrt{(0-1)^2 + (0-0)^2} + \sqrt{(1-0)^2 + (0-1)^2} = 1 + \sqrt{2}\).

Bằng cách tính độ dài của các đường đi khác theo cách này, ta thấy rằng độ dài trung bình của tất cả các đường đi là:

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

Input

2
-879 981
-866 890

Output

91.9238815543

Có hai đường đi để thăm các thị trấn: \(1 \to 2\) và \(2 \to 1\). Các đường đi này có cùng độ dài.

Giải thích ví dụ mẫu:

Ví dụ 1:

• Input: 3 0 0 1 0 0 1
• Giải thích: Có 6 cách đi qua 3 thị trấn, độ dài trung bình của các đường đi là khoảng 2.2761423749.

Ví dụ 2:

• Input: 2 -879 981 -866 890
• Giải thích: Chỉ có 2 đường đi giữa 2 thị trấn, và độ dài của chúng là 91.9238815543.
  

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House