Problem:


Score : 300 points

Problem Statement

There are N towns in a coordinate plane. Town i is located at coordinates (x_i, y_i). The distance between Town i and Town j is \sqrt{\left(x_i-x_j\right)^2+\left(y_i-y_j\right)^2}.

There are 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! paths.

Constraints

2 \leq N \leq 8

-1000 \leq x_i \leq 1000

-1000 \leq y_i \leq 1000

\left(x_i, y_i\right) \neq \left(x_j, y_j\right) (if i \neq j)

(Added 21:12 JST) All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

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}.

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.

The length of the path 1 → 2 → 3 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}.

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...

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



Sample input:
3
0 0
1 0
0 1


Sample output:
2.2761423749

Submission status: Accepted

Solution code:
from math import sqrt
from itertools import permutations

def dist(x0,y0,x1,y1):
  return sqrt((x0-x1)**2+(y0-y1)**2)

N=int(input())
x,y=[],[]
for _ in range(N):
  x_tmp,y_tmp=list(map(int,input().split()))
  x.append(x_tmp)
  y.append(y_tmp)
ls=list(permutations(list(range(N)),N))
ans=0
for l in ls:
  idx=0
  while idx+1<len(l):
    ans+=dist(x[l[idx]],y[l[idx]],x[l[idx+1]],y[l[idx+1]])
    idx+=1
print(ans/len(ls))

Submission status: Accepted

Solution code:
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial,sqrt
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis=[LI() for i in range(n)]
ans=0
for i in range(n):
    for j in range(n):
        ans+=sqrt((lis[i][0]-lis[j][0])**2+(lis[i][1]-lis[j][1])**2)
print(ans/n)

Submission status: Accepted

Solution code:
import math
from itertools import permutations

def dist(x0, y0, x1, y1):
    return math.sqrt((x0 - x1) ** 2 + (y0 - y1) ** 2)

def resolve():
    N = int(input())
    x, y = [], []
    for _ in range(N):
        x_tmp, y_tmp = list(map(int, input().split()))
        x.append(x_tmp)
        y.append(y_tmp)

    ls = list(permutations(list(range(N)), N))
    ans = 0
    for l in ls:
        idx = 0
        while idx + 1 < len(l):
            ans += dist(x[l[idx]], y[l[idx]], x[l[idx+1]], y[l[idx+1]])
            idx += 1

    print(ans / len(ls))
    return

resolve()

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
xy = []
for i in range(n):
    x,y = readInts()
    xy.append((x,y))
dist = 0
for x1,y1 in xy:
    for x2,y2 in xy:
        dist += ((x1-x2)**2 + (y1-y2)**2)**0.5
print(dist/n)

Submission status: Accepted

Solution code:
N = int(input())
XY = [list(map(int, input().split())) for i in range(N)]
ans = 0
for i in range(N):
    for j in range(i+1, N):
        ans += ((XY[i][0] - XY[j][0]) ** 2 + (XY[i][1] - XY[j][1]) ** 2) ** (1 / 2)
ans *= 2 / N
print(ans)

Submission status: Accepted

Solution code:
import itertools
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]

ans = []
for v in itertools.permutations(list(range(n)), n):
    a = 0
    for i in range(len(v)-1):
        x1,y1 = xy[v[i]][0], xy[v[i]][1]
        x2,y2 = xy[v[i+1]][0], xy[v[i+1]][1]
        a += ((x1-x2)**2+(y1-y2)**2)**0.5
    ans.append(a)
print(sum(ans)/len(ans))

Submission status: Accepted

Solution code:
from itertools import permutations
def dist(x,y):
    return ((x[0]-y[0])**2+(x[1]-y[1])**2)**0.5
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
cnt = 0
for z in permutations(range(N),N):
    for i in range(1,N):
        cnt += dist(X[z[i]],X[z[i-1]])
k = 1
for i in range(2,N+1):
    k = k*i
print(cnt/k)

Submission status: Accepted

Solution code:
import math
n=int(input())
towns=[]
for i in range(n):
  x,y=map(int,input().split())
  towns.append([x,y])
total=0
for i in range(n-1):
  for j in range(i+1,n):
    total+=math.sqrt((towns[i][0]-towns[j][0])**2+(towns[i][1]-towns[j][1])**2)
print(2*total/n)

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt

n=int(input())
lst=[list(map(int,input().split())) for i in range(n)]

kyori=[]
for i in range(n):
    kyori.append([])

for i in range(n):
    for j in range(n):
        kyori[i].append(sqrt((lst[i][0]-lst[j][0])**2 + (lst[i][1]-lst[j][1])**2))

pmt=list(permutations(range(0,n)))
ans=0
for i in range(len(pmt)):
    for j in range(n-1):
        ans+=kyori[pmt[i][j]][pmt[i][j+1]]

print(ans/len(pmt))

Submission status: Accepted

Solution code:
# coding: utf-8
import math
import itertools
N = int(input())
R  =[]
for i in range(N):
    x, y = map(int,input().split())
    R.append([x, y])
#print(R[0][0])
#L = copy.deepcopy(R)
l = [i for i in range(N)]
p = list(itertools.permutations(l,N))
S = 0
#print(p)
for v in p:
    for i in range(N-1):
        S += math.sqrt((R[v[i]][0]-R[v[i+1]][0])**2+(R[v[i]][1]-R[v[i+1]][1])**2)

ans = S / len(p)
print(ans)

Submission status: Accepted

Solution code:
import itertools

N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]

dis_count=[]
for i in itertools.permutations([i for i in range(1,N+1)],N):
    dis = 0
    for j in range(N-1):
        dis += ((xy[i[j]-1][0]-xy[i[j+1]-1][0])**2+(xy[i[j]-1][1]-xy[i[j+1]-1][1])**2)**0.5
    dis_count.append(dis)

print(sum(dis_count)/len(dis_count))

Submission status: Accepted

Solution code:
import math
N = int(input())


li = [list(map(int,input().split())) for i in range(N)]

from itertools import permutations
def func(a):
    if a==1:
        return 1
    return a*func(a-1)

counter = 0
for i in permutations(range(N)):
    x_now,y_now = li[i[0]]
    path = i[1:]
    for next in path:
        x_next,y_next = li[next]
        #print(x_next,y_next,x_now,y_now) 
        ok = (x_next-x_now)**2+(y_next-y_now)**2
        distans = math.sqrt(ok)
    
        counter += distans
 
        x_now,y_now  = x_next,y_next
        #print(counter)
    #print(i)
oppai = func(N)
print(counter/oppai)

Submission status: Accepted

Solution code:
import itertools
import math

n = int(input())
point = [tuple(map(int, input().split())) for i in range(n)]

numbers = 1
for i in range(1,n+1):
    numbers *= i
#nの階乗

route = list(itertools.permutations(point))

d = 0

for pattern in route:
    for i in range(n-1):
        d += math.sqrt((pattern[i][0]-pattern[i+1][0])**2 + (pattern[i][1]-pattern[i+1][1])**2)
        

ans = d / numbers

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt

N = int(input())
pos = {i: tuple(map(int, input().split())) for i in range(1, N + 1)}


total = 0
for i, permutation in enumerate(permutations([i for i in range(1, N + 1)]), 1):
    for j in range(N - 1):
        x_i, y_i = pos[permutation[j]]
        x_j, y_j = pos[permutation[j + 1]]
        dis = sqrt((x_i - x_j) ** 2 + (y_i - y_j) ** 2)
        total += dis

print(total / i)

Submission status: Accepted

Solution code:
n = int(input())
lst = []
for i in range(n):
  lst.append(tuple(map(int, input().split())))
dis = 0
for i in range(n - 1):
  for j in range(i + 1, n):
    dis += ((lst[i][0] - lst[j][0]) ** 2 + (lst[i][1] - lst[j][1]) ** 2) ** 0.5
print(dis * 2 / n)

Submission status: Accepted

Solution code:
N = int(input())
xy = []
for i in range(N):
    xy.append(list(map(int,input().split())))

from itertools import permutations
a=range(1,N+1)
ps = list(permutations(a))
#print(ps)

dammy=0
for p in ps:
    #print('p:',p)
    for j in range(1,N):
        dammy += ((xy[p[j-1]-1][0] - xy[p[j]-1][0])**2 + (xy[p[j-1]-1][1] - xy[p[j]-1][1])**2) ** (1/2)
        #print(dammy)
print(dammy/len(ps))

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt,factorial
n=int(input())
ans=0
distance=[list(map(int,input().split())) for i in range(n)]
town=[]
for i in range(n):
    town.append(i)
for a in list(permutations(town)):
    for j in range(n-1):
        ans+=sqrt((distance[a[j+1]][1]-distance[a[j]][1])**2+(distance[a[j+1]][0]-distance[a[j]][0])**2)
print(ans/(factorial(n)))

Submission status: Accepted

Solution code:
from itertools import combinations, permutations

N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]


dists = {i: {j: 0 for j in range(N)} for i in range(N)}
for i,j in combinations(range(N), 2):
    x1, y1 = xy[i]
    x2, y2 = xy[j]
    dists[i][j] = dists[j][i] = ((x1 - x2)**2 + (y1 - y2)**2)**(0.5)

factorial_of_N = 0
total_dist = 0.0
for route in permutations(range(N)):
    prev_i = route[0]
    factorial_of_N += 1
    for i in route[1:]:
        total_dist += dists[prev_i][i]
        prev_i = i

print(total_dist / factorial_of_N)

Submission status: Accepted

Solution code:
import itertools
import math
N=int(input())
L=[]
for i in range(N):
    x,y = map(int,input().split())
    L.append([x,y])

a=[]
for j in range(0,N):
    a.append(j)
ans=[]
for v in itertools.permutations(a, N):
    v=list(v)
    K=0
    for j in range(N-1):
        K+=math.sqrt((L[v[j+1]][0]-L[v[j]][0])**2+(L[v[j+1]][1]-L[v[j]][1])**2)
    ans.append(K)
    
print(sum(ans)/len(ans))

Submission status: Accepted

Solution code:
n=int(input())
x=[]
y=[]
for i in range(n):
    a,b=map(int,input().split())
    x.append(a)
    y.append(b)

ans=0

for i in range(n):
    for j in range(n):
        ans+=((x[i]-x[j])**2+(y[i]-y[j])**2)**0.5

print(ans/n)

Submission status: Accepted

Solution code:
from math import sqrt
N = int(input())
pts = []
for i in range(N):
    x,y = map(int,input().split())
    pts.append((x,y))
def fact(n):
    if n == 1:
        return 1
    return fact(n-1)*n
ans = 0
for i in range(N):
    for j in range(N):
        x1,y1 = pts[i]
        x2,y2 = pts[j]
        dx = x1-x2
        dy = y1-y2
        ans += fact(N-1)*(sqrt(dx**2+dy**2))
print(ans/fact(N))

Submission status: Accepted

Solution code:
import itertools
N =int(input())
X = [list(map(int,input().split())) for i in range(N)]
dist = 0
counter = 0
perm = list(itertools.permutations(list(range(N)),N))
for s in perm:
    idist = 0
    for i in range(N-1):
        idist +=( (X[s[i]][0]-X[s[i+1]][0])**2 + (X[s[i]][1]-X[s[i+1]][1])**2)**0.5
    dist += idist
    counter += 1
print(dist/counter)

Submission status: Accepted

Solution code:
import itertools as itr

N = int(input())
x = [0]*N
y = [0]*N
for i in range(N):
    x[i],y[i] = map(int,input().split())

L = list(range(N))
P = list(itr.permutations(L,N))

D = 0
for i in P:
    for j in range(N-1):
        D += ((x[i[j]] - x[i[j+1]])**2 + (y[i[j]] - y[i[j+1]])**2)**0.5

print(D / len(P))

Submission status: Accepted

Solution code:
from itertools import permutations

def main():
    def distance(x1, y1, x2, y2):
        return((abs(x1-x2)**2 + abs(y1-y2)**2) ** (1/2))
        
    n = int(input())
    l = list(range(n))
    perm = list(permutations(l, n))
    perm_l = len(perm)
    a = [0] * n
    b = [0] * n
    for i in range(n):
        a[i], b[i] = map(int, input().split())
    ans = 0
    for p in perm:
        for i in range(n-1):
            ans += distance(a[p[i]], b[p[i]], a[p[i+1]], b[p[i+1]])
    print(ans/perm_l)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import math

n = int(input())
distances = []
for index in range(n):
    distance = list(map(int, input().split()))
    distances.append(distance)

output = []
permutation = list(itertools.permutations(range(n)))
for p in permutation:
    total = 0
    for index in range(len(p) - 1):
        idx1, idx2 = p[index], p[index+1]
        d0 = distances[idx1]
        d1 = distances[idx2]
        
        total += math.sqrt((d0[0] - d1[0]) * (d0[0] - d1[0]) + (d0[1] - d1[1]) * (d0[1] - d1[1]))
    output.append(total)
print(sum(output) / len(permutation))

Submission status: Accepted

Solution code:
from itertools import permutations


def main():
    N = int(input())
    cities = [i for i in range(N)]
    xys = []
    for _ in range(N):
        xys.append(list(map(int, input().split())))

    combs = list(permutations(cities))
    sum_dist = 0
    for comb in combs:
        for i in range(len(comb)-1):
            idx1 = comb[i]
            idx2 = comb[i+1]
            sum_dist += (
                (xys[idx1][0] - xys[idx2][0]) ** 2 +
                (xys[idx1][1] - xys[idx2][1]) ** 2) ** 0.5
    print(sum_dist / len(combs))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
x=[]
y=[]
for i in range(n):
  a,b=map(int,input().split())
  x.append(a)
  y.append(b)
ans=0
for i in range(n):
  for j in range(n):
    ans+=((x[i]-x[j])**2+(y[i]-y[j])**2)**.5
print(ans/n)

Submission status: Accepted

Solution code:
from itertools import permutations
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]


pattern = list(permutations(range(n)))

ans = 0
for p in pattern:
    tmp = 0
    for i in range(n - 1):
        tmp += ((xy[p[i + 1]][0] - xy[p[i]][0])**2 +
                (xy[p[i + 1]][1] - xy[p[i]][1])**2)**0.5
    ans += tmp

print(ans / len(pattern))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import math
import itertools


def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力を取得
    """
    N = int(input())
    x, y = [], []
    for n in range(N):
        x_n, y_n = list(map(int, input().split()))
        x.append(x_n)
        y.append(y_n)

    return N, x, y


def get_distance(x: list, y: list, i: int, j: int) -> float:
    """
    町iと町jの間の距離を取得する.

    Args:\n
        x (list): 町のx座標
        y (list): 町のy座標
        i (int): 町
        j (int): 町

    Returns:\n
        float: 町iと町jの間の距離
    """
    return math.sqrt((x[i] - x[j])**2 + (y[i] - y[j])**2)


def get_path_length(N: int, distance: dict, path: list) -> float:
    """
    経路の長さを求める.

    Args:\n
        N (int): 町の数
        distance (dict): 町間の距離
        path (list): 経路

    Returns:\n
        float: 経路の長さ
    """
    path_length = 0
    for n in range(N - 1):
        path_length += distance[(path[n], path[n + 1])]

    return path_length


def main(N: int, x: list, y: list) -> None:
    """
    メイン処理.

    Args:\n
        N (int): 町の数
        x (list): 町のx座標
        y (list): 町のy座標
    """
    # 事前に町間の距離情報を作っておく
    distance = {}
    for i, j in itertools.product(range(N), repeat=2):
        distance[(i, j)] = get_distance(x, y, i, j)

    # 求解処理
    ans = 0
    for path in itertools.permutations(range(N)):
        ans += get_path_length(N, distance, path)
    ans /= math.factorial(N)

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N, x, y = get_input()

    # メイン処理
    main(N, x, y)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import math
import itertools

# 標準入力を取得
N = int(input())
x, y = [], []
for n in range(N):
    x_n, y_n = list(map(int, input().split()))
    x.append(x_n)
    y.append(y_n)


def get_distance(i: int, j: int) -> float:
    return math.sqrt((x[i] - x[j])**2 + (y[i] - y[j])**2)


def get_path_length(distance: dict, path: list) -> float:
    path_length = 0
    for n in range(N - 1):
        path_length += distance[(path[n], path[n + 1])]

    return path_length


# 求解処理
distance = {}
for i, j in itertools.product(range(N), range(N)):
    distance[(i, j)] = get_distance(i, j)

ans = 0
for path in itertools.permutations(range(N)):
    ans += get_path_length(distance, path)
ans /= math.factorial(N)

# 結果出力
print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

n = int(input())
posi_list = []
for _ in range(n):
  posi_list.append(list(map(int, input().split())))

city = [i for i in range(n)]
dist_list = []
for root in itertools.permutations(city):
  dist = 0
  for i in range(1,len(root)):
    now = root[i]-1
    prev = root[i-1]-1
    
    prev_x = posi_list[prev][0]
    prev_y = posi_list[prev][1]
    now_x = posi_list[now][0]
    now_y = posi_list[now][1]
    
    dist += np.sqrt((now_x-prev_x)**2 + (now_y-prev_y)**2)
  dist_list.append(dist)
  
print(np.mean(dist_list))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[2]:


import math


# In[7]:


N = int(input())
xy = []
for _ in range(N):
    xy.append(list(map(int, input().split())))


# In[8]:


dist = 0
for i in range(N):
    for j in range(i,N):
        dist += math.sqrt((xy[i][0]-xy[j][0])**2 + (xy[i][1]-xy[j][1])**2)
print(dist*2/N)


# In[ ]:

Submission status: Accepted

Solution code:
import sys
from itertools import permutations
from math import factorial

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def distance_nd(p, q):
    return sum((px - qx) ** 2.0 for px, qx in zip(p, q)) ** 0.5


def main():
    N = int(readline())
    P = [0] * N
    for i in range(N):
        P[i] = tuple(map(int, readline().split()))

    dist = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(i + 1, N):
            dist[i][j] = dist[j][i] = ((P[i][0] - P[j][0]) ** 2 + (P[i][1] - P[j][1]) ** 2) ** 0.5

    ans = 0
    for perm in permutations(range(N)):
        for i in range(N - 1):
            ans += dist[perm[i]][perm[i + 1]]

    ans /= factorial(N)

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import math
N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
distance = 0
pt = list(itertools.permutations(xy, N))
bunbo = len(pt)

for i in pt:
    for j in range(N-1):
        distance += math.sqrt((i[j][0] - i[j+1][0])**2 + (i[j][1] - i[j+1][1])**2)


print(distance/bunbo)

Submission status: Accepted

Solution code:
import itertools
N = int(input())
xy_list = [list(map(int, input().split())) for _ in range(N)]

ans = 0
num = 0
for xy in itertools.permutations(xy_list):
    ans_pre = 0
    for i in range(N-1):
        ans_pre += ((xy[i][0]-xy[i+1][0])**2 + (xy[i][1]-xy[i+1][1])**2)**(0.5)
    num += 1
    ans += ans_pre
print(ans/num)

Submission status: Accepted

Solution code:
n = int(input())
xyn = []
for _ in range(n):
    x, y = map(int, input().split())
    xyn.append([x,y])
import itertools
ls = list(itertools.permutations(range(1, n+1)))


leng=0

for i in ls:
    for j in range(len(i)-1):
        z=i[j]
        a=i[j+1]
        leng += ((xyn[z-1][0]-xyn[a-1][0])**2+(xyn[z-1][1]-xyn[a-1][1])**2)**0.5

ans = leng/len(ls)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]

d = 0
for x, y in l:
    for z, w in l:
        d += ((x-z)**2+(y-w)**2)**0.5
print(d/n)

Submission status: Accepted

Solution code:
from itertools import permutations
import math

n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]
m = math.factorial(n)
p = list(permutations(l))
d = 0

for i in range(m):
    for j in range(n-1):
        x = p[i][j][0] - p[i][j-1][0]
        y = p[i][j][1] - p[i][j-1][1]
        d += math.sqrt(x**2 + y**2)

print(d/m)

Submission status: Accepted

Solution code:
import numpy as np

def distance(x1, x2):
    return np.sqrt((x1[0] - x2[0])**2 + (x1[1] - x2[1])**2)

N = int(input())
X = []

N_exs = [0, 1, 2, 6, 24, 120, 720, 5040, 40320]

for _ in range(N):
    A, B = map(int, input().split())
    X.append([A, B])

total = 0
for i in range(N):
    for j in range(N-1, i, -1):
        if i == j:
            continue
        total += distance(X[i], X[j])

num = int((N * N - N) / 2)

# 1パターンあたりにN-1個ルートがあり、どのルートも均等に存在する
ans = total * (N-1) / num

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import permutations as p

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n = readInt()
xy = [readInts() for i in range(n)]
l = list(p(list(range(0,n))))
length = len(l)
sumDis = 0
for i in l:
	for j in range(n-1):
		sumDis += ((xy[i[j+1]][0]-xy[i[j]][0])**2+(xy[i[j+1]][1]-xy[i[j]][1])**2)**0.5

print(sumDis/length)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import permutations as p

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n = readInt()
xy = [readInts() for i in range(n)]
l = p(list(range(0,n)))
length = len(list(p(list(range(0,n)))))
sumDis = 0
for i in l:
	for j in range(n-1):
		sumDis += ((xy[i[j+1]][0]-xy[i[j]][0])**2+(xy[i[j+1]][1]-xy[i[j]][1])**2)**0.5

print(sumDis/length)

Submission status: Accepted

Solution code:
import itertools
def Cal_Dist(i,j):
    a=((i[0]-j[0])**2+(i[1]-j[1])**2)**0.5
    return a

N=int(input())

town=[[0]*2 for i in range(N)]
for i in range (N):
    xy=list(map(int,input().split()))
    town[i]=xy
R=list(itertools.permutations(range(N)))

distance=[]


for k in range(len(R)):
    temp_town=[]
    for h in range(N):
        temp_town.append(town[R[k][h]])
    
    temp_distance=[]
    for i in range (N-1):
        distance_sections=Cal_Dist(temp_town[i],temp_town[i+1])
        temp_distance.append(distance_sections)
    else:
        distance.append(sum(temp_distance))
        # print(a,b,c,temp_distance)

# print(town)
# print(R)
print(sum(distance)/len(R))

Submission status: Accepted

Solution code:
N = int(input())
X = []
Y = []

for i in range(N):
  x, y = map(int, input().split())
  X.append(x)
  Y.append(y)
  
sum_all = 0
for i in range(N):
  for j in range(i+1, N):
    sum_all += float((X[j]-X[i])**2 + (Y[j]-Y[i])**2) ** (1/2)
    
div = N/2
print(sum_all/div)

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, XY):
    from math import sqrt, factorial
    road_map = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            road_map[i][j] = sqrt((XY[i][0] - XY[j][0]) ** 2 + (XY[i][1] - XY[j][1]) ** 2)

    def dfs(now_town, visited, distance):
        visited[now_town] = 1
        if sum(visited) == N:
            return distance
        d = 0
        for i in range(N):
            if visited[i] == 0:
                d += dfs(i, visited.copy(), distance + road_map[now_town][i])
        return d

    sum_distance = 0
    for i in range(N):
        sum_distance += dfs(i, [0] * N, 0)

    print(sum_distance / factorial(N))


if __name__ == '__main__':
    # S = input()
    N = int(input())
    XY = []
    for _ in range(N):
        XY.append([int(i) for i in input().split()])
    solve(N, XY)

Submission status: Accepted

Solution code:
import math
import itertools

N = int(input())
position = [list(map(int, input().split())) for _ in range(N)]
town = list(range(N))
distance =list2 = [[0 for i in range(N)] for j in range(N)]
average = 0

for i in range(N):
  for j in range(N):
    distance[i][j] = math.sqrt((position[i][0] - position[j][0])**2 
                               + (position[i][1] - position[j][1])**2)

for order in itertools.permutations(town, N):
  for i in range(N-1):
    average += distance[order[i]][order[i+1]]
average /= math.factorial(N)

print(average)

Submission status: Accepted

Solution code:
import itertools
import math
n = int(input())
x,y = [],[]
for _ in range(n):
  a,b = map(int,input().split())
  x.append(a)
  y.append(b)

pat = itertools.permutations(range(n),n)
distsum = 0
for k in pat:
  dist = 0
  for i in range(n-1):
    dist += ((x[k[i+1]]-x[k[i]])**2+(y[k[i+1]]-y[k[i]])**2)**(1/2)
  distsum += dist
print(distsum/math.factorial(n))

Submission status: Accepted

Solution code:
from itertools import permutations
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]

ans = 0
count = 0
for i in permutations(range(n), n):
  for j in range(n-1):
    ans += ((xy[i[j]][0] - xy[i[j+1]][0])**2 + (xy[i[j]][1] - xy[i[j+1]][1])**2)**0.5
  count += 1

print(ans/count)

Submission status: Accepted

Solution code:
n=int(input())
x=[]
y=[]
for i in range(n):
  a,b=map(int,input().split())
  x.append(a)
  y.append(b)
sm=0
for i in range(n):
  for j in range(n):
    sm+=((x[i]-x[j])**2+(y[i]-y[j])**2)**0.5
print(sm/n)

Submission status: Accepted

Solution code:
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
ans=0
for i in range(n-1):
    for j in range(i+1,n):
        x1,y1=xy[i]
        x2,y2=xy[j]
        ans+=((x1-x2)**2+(y1-y2)**2)**(1/2)
ans/=n/2
print(ans)

Submission status: Accepted

Solution code:
import math
N=int(input())
x = []
for i in range(N):
    x.append(list(map(int,input().split())))
all_route=math.factorial(N)
route_sum=0
for i in range(N):
    for j in range(i+1,N):
        route_sum+=math.sqrt((x[i][0]-x[j][0])**2+(x[i][1]-x[j][1])**2)*((all_route*2)//N)
print(route_sum/all_route)

Submission status: Accepted

Solution code:
N = int(input())
xy = []
for n in range(N):
    x, y = [int(s) for s in input().split(' ')]
    xy.append((x, y))
total = 0
pattern = 1
for n in range(N):
    pattern *= (1 + n)
    for m in range(n + 1, N):
        x0, y0 = xy[n]
        x1, y1 = xy[m]
        total += ((x0 - x1) ** 2 + (y0 - y1) ** 2) ** 0.5
print(total * pattern / N * 2 / pattern)

Submission status: Accepted

Solution code:
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = int(input())
stock = []
for i in range(n):
	x, y = [int(j) for j in input().split()]
	lengths = []
	for xx, yy, _ in stock:
		lengths.append(((x - xx) * (x - xx) + (y - yy) * (y - yy)) ** 0.5)
	stock.append((x, y, lengths))

sum_length = 0
n_appear_by = math.factorial(n) * (n - 1) / n
for _, _, ls in stock:
	for l in ls:
		sum_length += l
print(sum_length * (n - 1) / combinations_count(n, 2))

Submission status: Accepted

Solution code:
import os, sys, re, math

N = int(input())
XY = []

for i in range(N):
    XY.append([int(n) for n in input().split()])

V = 0
for i in range(N):
    for j in range(N):
        if i != j:
            V += math.sqrt((XY[i][0] - XY[j][0]) ** 2 + (XY[i][1] - XY[j][1]) ** 2)

S = [0, 0, 1, 3, 6, 10, 15, 21, 28]
T = math.factorial(N)
m = T * (N - 1) // S[N] // 2

print(m * V / T)

Submission status: Accepted

Solution code:
import itertools
import math

N = int(input())

loc = [[int(s) for s in input().split()] for _ in range(N)]

dist = [[0] * N for _ in range(N)]

for i in range(N):
    for j in range(i + 1, N):
        dist[i][j] = math.sqrt((loc[i][0] - loc[j][0])** 2 + (loc[i][1] - loc[j][1])** 2)
        dist[j][i] = dist[i][j]

d_cnt = 0
cnt = 0
for per in itertools.permutations(list(range(N)), N):
    for i, j in zip(per, per[1:]):
        d_cnt += dist[i][j]
    cnt += 1

print(d_cnt / cnt)

Submission status: Accepted

Solution code:
import os, sys, re, math

N = int(input())
XY = []

for i in range(N):
    XY.append([int(n) for n in input().split()])

d = []
for i in range(N):
    dd = []
    for j in range(N):
        if i == j:
            dd.append(0)
        else:
            v = math.sqrt((XY[i][0] - XY[j][0]) ** 2 + (XY[i][1] - XY[j][1]) ** 2)
            dd.append(v)
    d.append(dd)

S = [0, 0, 1, 3, 6, 10, 15, 21, 28]
T = math.factorial(N)
m = T * (N - 1) // S[N] // 2

print(m * sum([sum(dd) for dd in d]) / T)

Submission status: Accepted

Solution code:
n = int(input())
xys = []
for i in range(n):
    x, y = list(map(int, input().split(' ')))
    xys.append((x, y))
# 全部の組み合わせを足して割った数と同じ？
temp = 0.0
for i in range(n):
    for j in range(n):
        temp += (((xys[i][0] - xys[j][0]) ** 2 + (xys[i][1] - xys[j][1]) ** 2) ** 0.5)
print(temp / n)

Submission status: Accepted

Solution code:
import math

n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
print(sum(math.hypot(xy[i][0] - xy[j][0], xy[i][1] - xy[j][1]) for i in range(n) for j in range(n)) / n)

Submission status: Accepted

Solution code:
import math
import itertools

n = int(input())
x = []
y = []
for _ in range(n):
    xi, yi = map(int, input().split())
    x.append(xi)
    y.append(yi)

path_len = 0
path = []

s = [i for i in range(n)]
paths = list(itertools.permutations(s))
path_lens = []

for path in paths:
    path_len = 0
    for i in range(len(path)-1):
        path_len += float(math.sqrt((x[path[i]]-x[path[i+1]])**2 +
                                    (y[path[i]]-y[path[i+1]])**2))
    path_lens.append(path_len)

print(sum(path_lens) / len(paths))

Submission status: Accepted

Solution code:
from itertools import permutations
import math
N = int(input())
xy = [tuple(map(int,input().split())) for _ in range(N)]
city = list(permutations(xy))
all_len = 0
for i in city:
  sum_len = 0
  for j in range(1,N):
    sum_len += ((i[j][0]-i[j-1][0])**2 +(i[j][1]-i[j-1][1])**2)**0.5
  all_len += sum_len
print(all_len/len(city))

Submission status: Accepted

Solution code:
from itertools import combinations

N = int(input())
town = [tuple(map(int,input().split())) for _ in range(N)]
all_len = 0

for x, y in combinations(town,2):
  all_len += ((x[0]-y[0])**2 + (x[1]-y[1])**2)**0.5

result = (all_len*2)/N
print(result)

Submission status: Accepted

Solution code:
#<100q.順列全探索>
#<15>
from itertools import combinations
n = int(input())
town = []
for i in range(n):
    x, y = map(int,input().split())
    town.append((x,y))

ans = 0
for i, j in combinations(town, 2):
    
    ans += ((i[0] - j[0]) ** 2 + (i[1] - j[1]) ** 2) ** (0.5)
print(2 * ans / n)