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

Solution (Python):
import itertools
import math
n = int(input())
x,y = [0] * n, [0] * n
for i in range(n):
  dx,dy = map(int,input().split())
  x[i], y[i] = dx, dy
ans = 0
for i in itertools.permutations(range(n)):
  i = list(i)
  for j in range(n - 1):
    ans += math.sqrt(pow(x[i[j]] - x[i[j + 1]], 2) + pow(y[i[j]] - y[i[j + 1]], 2))
num = 1
for i in range(n):
  num *= i + 1
print(ans / num)

Solution (Python):
N = int(input())

xy_list = list()

for _ in range(N):
    xy_list.append( tuple(map(int, input().split() )) )




from math import sqrt

def calc_dist(p1, p2):
    p1_x, p1_y = p1
    p2_x, p2_y = p2

    return sqrt((p2_x-p1_x)**2 + (p2_y-p1_y)**2)

from itertools import permutations
A_perm = permutations(xy_list, N)

sum_all = 0
cnt = 0
for a in A_perm:
    sum_dist = 0
    
    for i in range(len(a)-1):
        sum_dist = sum_dist + calc_dist(a[i], a[i+1])
    

    sum_all = sum_all + sum_dist
    cnt = cnt + 1

print(sum_all / cnt)

Solution (Python):
from math import sqrt
n = int(input())
X = []
Y = []
s = 0
for i in range(n):
    x,y = input().split()
    X.append(int(x))
    Y.append(int(y))

for i in range(n):
    for j in range(n):
        a = X[i] - X[j]
        b = Y[i] - Y[j]
        s += sqrt(a*a + b*b)
print(s/n)

Solution (Python):
import math
import itertools




N = int(input())

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

paths = []
for one_case in itertools.permutations(P):
    sum_path = 0
    for i in range(len(P)):
        if i == len(P) - 1:
            break
        sum_path = sum_path + math.sqrt(
            (one_case[i][0] - one_case[i + 1][0]) ** 2 + (one_case[i][1] - one_case[i + 1][1]) ** 2)
    paths.append(sum_path)

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

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce


import sys
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')



n = I()
XY = LIR(n)
D = [[0]*n for _ in range(n)]
for i, j in combinations(range(n), 2):
    x1 = XY[i][0]
    y1 = XY[i][1]
    x2 = XY[j][0]
    y2 = XY[j][1]
    D[i][j] = sqrt((x1-x2)**2+(y1-y2)**2)

tmp = 0
for Z in permutations(range(n), n):
    a = 0
    for i in range(n-1):
        b = min(Z[i], Z[i+1])
        c = max(Z[i], Z[i+1])
        a += D[b][c]
    tmp += a
print(tmp/factorial(n))

Solution (Python):
from math import sqrt
n = int(input())
x,y,s = [],[],0
for _ in range(n):
    a,b = map(int,input().split())
    x.append(a)
    y.append(b)
for i in range(n):
    for j in range(n):
        a = x[i]-x[j]
        b = y[i]-y[j]
        s += sqrt(a*a+b*b)
print(s/n)

Solution (Python):
n = int(input())
ls = [list(map(int,input().split())) for i in range(n)]
a = 0
for j in range(n):
    for k in range(n):
        if j < k:
            a += ((ls[k][0]-ls[j][0])**2+(ls[k][1]-ls[j][1])**2)**(1/2)
b = a/(n*(n-1)/2)
print(b*(n-1))

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

Solution (Python):
from itertools import permutations
from math import factorial
n = int(input())
patern = factorial(n)
town = [list(map(int, input().split())) for _ in range(n)]
ans = 0
for rute in permutations(range(n)):
    road = 0
    for i in range(n-1):
        x,y = town[rute[i]]
        nx,ny = town[rute[i+1]]
        road += ((x-nx)**2 + (y-ny)**2)**(1/2)
    ans += road
print(ans/patern)

Solution (Python):
def dist(i, j):
    dx = x[i] - x[j]
    dy = y[i] - y[j]
    return pow(dx * dx + dy * dy, 0.5)


xys = []
x = []
y = []

n = int(raw_input())

for _ in range(n):
    xys.append(map(int, raw_input().split()))

for xy in xys:
    x.append(xy[0])
    y.append(xy[1])

result = 0.0

for i in range(n):
    for j in range(i, n):
        result += (dist(i, j)) * 2 / n

print(result)

Solution (Python):

import math
import copy

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

for n in range(N):
    x, y = map(int, input().split())
    x_y_list.append([x, y])


visited = [False] * N
d_list = []
log_list = []

def dfs(distance, ex_coord, log):

    if all(visited):
        d_list.append(distance)
        log_list.append(copy.copy(log))

        return

    for i in range(N):
        if visited[i]:
            continue
        else:
            tmp = 0
            if ex_coord != []:
                tmp = (ex_coord[0] - x_y_list[i][0]) ** 2 + (ex_coord[1] - x_y_list[i][1]) ** 2
                tmp = math.sqrt(tmp)
                distance += tmp

            visited[i] = True
            log.append(i + 1)
            dfs(distance, x_y_list[i], log)
            del log[-1]
            visited[i] = False
            distance -= tmp

log_tmp = []
dfs(0, [], log_tmp)
print(sum(d_list) / len(d_list))

Solution (Python):
import itertools,math
n=int(input())
t=[list(map(int,input().split())) for i in range(n)]
s=[i for i in range(n)]
l=list(itertools.permutations(s))
tmp=[]
for i in l:
    dis=0
    for j in range(n-1):
        x1=t[i[j+1]][0]
        x2=t[i[j]][0]
        y1=t[i[j+1]][1]
        y2=t[i[j]][1]
        dis+=((x2-x1)**2+(y2-y1)**2)**(1/2)
    tmp.append(dis)
print(sum(tmp)/math.factorial(n))

Solution (Python):
import itertools
import math

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

distance = 0
for v in itertools.permutations(index):
    for i in range(n-1):
        distance += math.sqrt((x[v[i]] - x[v[i+1]]) **
                              2 + (y[v[i]]-y[v[i+1]])**2)


print(distance/math.factorial(n))

Solution (Python):
import itertools

N = int(input())
N_list = [int(x) for x in range(N)]
com_N_list = list(itertools.permutations(N_list,N))


point_list = []
for _ in range(N):
    x,y = map(int,input().split())
    point_list.append((x,y))

dis_list = []

for j in com_N_list:
    dis = 0
    for i in range(N-1,0,-1):
        dis += ((point_list[j[i]][0]-point_list[j[i-1]][0])**2 + (point_list[j[i]][1]-point_list[j[i-1]][1])**2)**(1/2)
    dis_list.append(dis)

ans = sum(dis_list)/(len(com_N_list))
print(ans)

Solution (Python):
import itertools
import math

N = int(input())

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

a = []

for i in range(1,N+1):
    a += [i]

b = []

for v in itertools.permutations(a, N):
    b.append(list(v))

ancerL = []

for i in range(len(b)):
    ancer = 0
    for j in range(N-1):
        
        combined1 = [x - y for (x, y) in zip(q[b[i][j+1]-1], q[b[i][j]-1])]
        
        ancer += math.sqrt(combined1[0]**2 + combined1[1]**2)
       
    ancerL.append(ancer)
    
print(sum(ancerL) / len(ancerL))

Solution (Python):
import itertools

N = int(input())
X = [list(map(int, input().split())) for i in range(N)]
x = list(itertools.permutations(range(N),N))
res = 0
for a in x:
    for i in range(N - 1):
        res += ((X[a[i]][0] - X[a[i + 1]][0]) ** 2 + (X[a[i]][1] - X[a[i + 1]][1]) ** 2) ** 0.5
print(res / len(x))

Solution (Python):
import itertools

N = int(input())
X = [list(map(int, input().split())) for i in range(N)]
x = list(itertools.permutations(range(N)))
res = 0
for a in x:
    for i in range(N - 1):
        res += ((X[a[i]][0] - X[a[i + 1]][0]) ** 2 + (X[a[i]][1] - X[a[i + 1]][1]) ** 2) ** 0.5
print(res / len(x))

Solution (Python):
from itertools import permutations
N = int(input())
x = [0]*N
y = [0]*N
route = list(permutations(range(N)))

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

ans = 0
for r in route:
    for l in range(len(r)-1):
        tmp = ((x[r[l]] - x[r[l+1]])**2 + (y[r[l]] - y[r[l+1]])**2)**0.5
        ans += tmp

print(ans / len(route))

Solution (Python):
import itertools
N = int(input())
zahyo =[list(map(int,input().split())) for _ in range(N)]
N_list = [i for i in range(N)]
P = itertools.permutations(N_list,N)
P = list(P)
sm = 0
for p in P:
    for i,j in zip(p,p[1:]):
        xi,yi = zahyo[i]
        xj,yj = zahyo[j]
        sm += (((xi-xj)**2+(yi-yj)**2)**0.5)
print(sm/len(P))

Solution (Python):
N = int(input())
towns = list()
flag = [False for i in range(N)]


def factorial(n):
    if n < 1:
        return 1
    return n * factorial(n - 1)


def distance(x, y):
    return ((x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2) ** 0.5


def dfs(n, prev_town):

    if n == N - 1:
        return 0

    res = 0

    for i, town in enumerate(towns):
        if flag[i] is False:
            flag[i] = True
            res += dfs(n + 1, town)
            res += distance(prev_town, town) * factorial(N - n - 2)
            flag[i] = False

    return res


for i in range(N):
    towns.append(tuple(map(int, input().split())))

ans = 0

for i, town in enumerate(towns):
    flag[i] = True
    ans += dfs(0, towns[i])
    flag[i] = False

ans = ans / factorial(N)

print(ans)

Solution (Python):
N = int(input())

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

print(sum/N)

Solution (Python):


N = int(input())
P = []
for _ in range(N):
    x, y = map(int, input().split())
    P.append((x, y))

D = []
for i in range(N):
    for j in range(i + 1, N):
        dist = (((P[i][0] - P[j][0]) ** 2) +
                ((P[i][1] - P[j][1]) ** 2)) ** (1 / 2)
        D.append(dist)

print(sum(D) / len(D) * (N - 1))

Solution (Python):
import itertools
import math
N=int(input())
l=[]
mem=[]
P=list(itertools.permutations(range(1,N+1)))
for i in range(N):
    l.append(list(map(int,input().split())))
for i in range(len(P)):
    mem.append(0)
    for j in range(len(P[i])-1):
        pos1 = P[i][j]-1
        pos2 = P[i][j+1]-1
        mem[i] += math.sqrt(((l[pos1][0]-l[pos2][0])**2) + ((l[pos1][1]-l[pos2][1])**2))
print(sum(mem)/len(mem))

Solution (Python):
import itertools
import math
N = int(input())
town = []
for _ in range(N):
  town.append(list(map(int, input().split())))
ind = [i for i in range(N)]
dis = 0
for ind in itertools.permutations(ind):
  for j in range(N):
    if j == N-1:
      break
    dis += ((town[ind[j]][0] - town[ind[j+1]][0])**2 + (town[ind[j]][1] - town[ind[j+1]][1])**2)**0.5
print(dis/math.factorial(N))

Solution (Python):
import itertools
import math
n = int(input())
lis = [x for x in range(n)]
permutations_lis = itertools.permutations(lis)
xy = [list(map(int,input().split())) for i in range(n)]
judge = []
for i in permutations_lis:
  count = 0
  first = i[0]
  for p in i:
    count += math.sqrt((xy[p][0]-xy[first][0])**2+(xy[p][1]-xy[first][1])**2)
    first = p
  else:
    judge.append(count)
print(sum(judge)/len(judge))

Solution (Python):
import itertools
N=int(input())
point=[]
for _ in range(N):
    x,y=map(int,input().split())
    point.append([x,y])
nums=[i for i in range(1,N+1)]
perm=list(itertools.permutations(nums,N))
dist=0

for pattern in perm:
    tmp_dist=0
    for i in range(N-1):
        tmp_dist+=((point[pattern[i]-1][0]-point[pattern[i+1]-1][0])**2+(point[pattern[i]-1][1]-point[pattern[i+1]-1][1])**2)**0.5
    dist+=tmp_dist
print(dist/len(perm))

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)

int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): return k.join(list(map(str, lst)))
INF = float('inf')
from math import sqrt
from itertools import permutations
def solve():
    n = II()

    town = []
    for i in range(n):
        x, y = MI()
        town.append((x, y))

    def f(t1, t2):
        x1, y1 = t1
        x2, y2 = t2
        return sqrt( (x1 - x2) ** 2 + (y1 - y2) ** 2)

    tot = 0
    cnt = 0
    for t in permutations(town, n):
        cnt += 1
        d = 0
        
        for i in range(n-1):
            j = i + 1
            d = f(t[i], t[j])
            
            tot += d

    print(tot / cnt)


if __name__ == '__main__':
    solve()

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

dst = 0
for i in range(n-1):
    for j in range(i+1, n):
        dst += ((pos[i][0]-pos[j][0])**2 + (pos[i][1]-pos[j][1])**2)**(1/2)
print(dst*2/n)

Solution (Python):
import itertools
N = int(input())
XY = [[int(i) for i in input().split()] for j in range(N)]

All = list(itertools.permutations(range(N)))

def euqlid(a1,a2,b1,b2):
    return pow((a1-a2)**2+(b1-b2)**2,0.5)
    
ans = 0
co = 0
for i in All:
    count = 0
    i = list(i)
    x,y = XY[i[0]]
    for j in i[1:]:
        s,t = XY[j]
        count += euqlid(x,s,y,t)
        x,y = s,t
    ans += count
    co += 1

print(ans/co)

Solution (Python):
import itertools

n = int(input())
xy_inputs = [[int(j) for j in input().split()]for i in range(n)]

dist_map = [[0 for i in range(n)] for i in range(n)]
for i in range(n):
    for j in range(n):
        x1,y1 = map(int,xy_inputs[i])
        x2,y2 = map(int,xy_inputs[j])
        dist = ((x1-x2)**2+(y1-y2)**2)**0.5
        dist_map[i][j]=dist
        dist_map[j][i]=dist

ans=0
li = list(itertools.permutations([i for i in range(n)],n))
for l in li:
    for i in range(len(l)-1):
        ans+=dist_map[l[i]][l[i+1]]

print(ans/len(li))

Solution (Python):
n=int(input())
lis=[]
for i in range(n):
  lis.append(list(map(int,input().split())))

summ=0
for i in range(0,n-1):
  for j in range(i+1,n):
    dis=((lis[i][0]-lis[j][0])**2+(lis[i][1]-lis[j][1])**2)**(1/2)
    summ+=dis
print(summ*2/n)

Solution (Python):


import itertools

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

def calcDist(Y):
    dist = 0
    for i in range(1, len(Y)):
        dist += pow(pow(P[Y[i]][0] - P[Y[i-1]][0], 2) + pow(P[Y[i]][1] - P[Y[i-1]][1], 2), 0.5)
    return dist

def dfs(X):
    global ans
    if len(X)==N:
        ans.append(calcDist(X))
        return
    for i in range(N):
        if i not in X:
            X.append(i)
            dfs(X)
            X.pop()

ans = []
X = []


for X in itertools.permutations(range(N),N):
    ans.append(calcDist(X))

print(sum(ans)/len(ans))

Solution (Python):


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

def calcDist(Y):
    dist = 0
    for i in range(1, len(Y)):
        dist += pow(pow(P[Y[i]][0] - P[Y[i-1]][0], 2) + pow(P[Y[i]][1] - P[Y[i-1]][1], 2), 0.5)
    return dist

def dfs(X):
    global ans
    if len(X)==N:
        ans.append(calcDist(X))
        return
    for i in range(N):
        if i not in X:
            X.append(i)
            dfs(X)
            X.pop()

ans = []
X = []
dfs(X)

print(sum(ans)/len(ans))

Solution (Python):
import math

n = int(input())
xyn = [None] * n
for i in range(n):
    xyn[i] = list(map(int, input().split(' ')))

t2t = []

for i in range(n):
    for j in range(n):
        if i == j:
            continue
        else:
            dis = math.sqrt((xyn[i][0] - xyn[j][0]) ** 2 + (xyn[i][1] - xyn[j][1]) ** 2)
            t2t.append(dis)

ave = sum(t2t) / len(t2t) * (n - 1)

print(ave)

Solution (Python):
import math
import itertools
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
def distance(x1, y1, x2, y2):
    return math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))

dist = 0
cnt = 0
for p in itertools.permutations(range(n)):
    for i in range(n-1):
        dist += distance(xy[p[i]][0], xy[p[i]][1], xy[p[i+1]][0], xy[p[i+1]][1])
    cnt += 1
ans = dist / cnt
print(ans)

Solution (Python):
import itertools
import math

n = int(input())
num = list(list(map(int, input().split())) for i in range(n))

num = list(itertools.permutations(num))

count = 0

for i in num:
  for j in range(len(i) - 1):
    count += math.sqrt(((i[j][0] - i[j + 1][0]) ** 2 + (i[j][1] - i[j + 1][1]) ** 2))

print(count/math.factorial(n))

Solution (Python):
n=int(input())
L=[]
for i in range(n):
    L.append(list(map(int,input().split())))

if n==2:
    print(((L[0][0]-L[1][0])**2+(L[0][1]-L[1][1])**2)**0.5)
else:
    s=0
    for p in range(n):
        for q in range(n):
            s+=((L[p][0]-L[q][0])**2+(L[p][1]-L[q][1])**2)**0.5
    print(s*((n-1)/(n*(n-1))))

Solution (Python):
from math import factorial
from itertools import permutations
def main():
    n = int(input())
    town_coor = []
    for _ in range(n):
        town_coor.append(tuple(map(int, input().split())))

    dists = [[0]*n for _ in range(n)]
    for j1 in range(n):
        for j2 in range(n):
            dists[j1][j2] = ((town_coor[j1][0] - town_coor[j2][0])**2 + (town_coor[j1][1] - town_coor[j2][1])**2)**0.5


    towns = [i for i in range(n)]
    roads = permutations(towns, n)
    sum_roads = 0
    for road in roads:
        sum_road = 0
        for i1 in range(n-1):
            sum_road += dists[road[i1]][road[i1+1]]
        sum_roads += sum_road
    print(sum_roads / factorial(n))

if __name__ == '__main__':
    main()

Solution (Python):
from math import factorial
from itertools import permutations
def main():
    n = int(input())
    town_coor = []
    for _ in range(n):
        town_coor.append(tuple(map(int, input().split())))

    towns = [i for i in range(n)]
    roads = permutations(towns, n)
    sum_roads = 0
    for road in roads:
        sum_road = 0
        for i1 in range(n-1):
            sum_road += ((town_coor[road[i1]][0] - town_coor[road[i1 +1]][0])**2 + (town_coor[road[i1]][1] - town_coor[road[i1 +1]][1])**2)**0.5
        sum_roads += sum_road
    print(sum_roads / factorial(n))

if __name__ == '__main__':
    main()

Solution (Python):
import math
N = int(input())
P = [(0, 0)]
for i in range(N):
    x, y = [int(_) for _ in input().split()]
    P.append((x, y))

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

print(s/N)

Solution (Python):
import math
import itertools

N = int(input())

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



route = itertools.permutations([i for i in range(N)], N)
cnt = 0

for r in route:
    for i in range(N-1):
        xi = xy[r[i]][0]
        xj = xy[r[i+1]][0]
        yi = xy[r[i]][1]
        yj = xy[r[i+1]][1]
        cnt += math.sqrt((xi-xj)**2 + (yi-yj)**2)

print(cnt/math.factorial(N))

Solution (Python):
import itertools
import math


def main():
    n = int(input())
    town = [i for i in range(1, n + 1)]
    comb = list(itertools.permutations(town))
    pos = []
    for i in range(n):
        pos.append(list(map(int, input().split())))
    calc = []
    for c in comb:
        tmp = 0
        for i in range(0, len(c) - 1):
            tmp += distance(pos[c[i] - 1], pos[c[i + 1] - 1])
        calc.append(tmp)
    mea = sum(calc) / len(calc)
    print(mea)


def distance(p, pp):
    return math.sqrt(((p[0] - pp[0]) **2) + ((p[1] - pp[1]) **2))


if __name__ == '__main__':
    main()

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

from itertools import permutations
ways = list(permutations(range(n)))

from math import sqrt

def d(x1, y1, x2, y2):
    return sqrt((x1-x2)**2 + (y1 - y2)**2)

c=0

for way in ways:
    for i in range(len(way) - 1):
        c += d(x[way[i]], y[way[i]], x[way[i+1]], y[way[i+1]])

ans = c / len(ways)
print(ans)

Solution (Python):
from math import sqrt

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

result = 0
for i in range(n):
    for j in range(n):
        if i != j:
            result += sqrt((xy[i][0] - xy[j][0])**2 + (xy[i][1] - xy[j][1])**2)

print(result/n)

Solution (Python):
import itertools
import math

n = int(input())
dots = [list(map(int, input().split())) for _ in range(n)]
cities = list(range(n))

res = 0
cnt = 0
for pattern in itertools.permutations(cities, len(cities)):
    cnt += 1
    for i in range(n-1):
        res += math.sqrt((dots[pattern[i]][0] - dots[pattern[i+1]][0]) ** 2 + (dots[pattern[i]][1] - dots[pattern[i+1]][1]) ** 2)


print(res/cnt)

Solution (Python):
n = int(input())
place = []
for _ in range(n):
    place.append(list(map(int, input().split())))
    
import itertools
route = list(itertools.permutations(range(n), n))

import math

ans = 0
for i in range(len(route)):
    dist = 0
    for j in range(n-1):
        dist += math.sqrt((place[route[i][j+1]][0] - place[route[i][j]][0])**2 + (place[route[i][j+1]][1] - place[route[i][j]][1])**2)
    
    ans += dist

print(ans/len(route))

Solution (Python):
import itertools
import math

n = int(input())
x_y = [list(map(int, input().split())) for _ in range(n)]
dist = 0
town = [i for i in range(n)]
root_lis = itertools.permutations(town)
for one_case in root_lis:
    x_prev, y_prev = x_y[one_case[0]][0], x_y[one_case[0]][1]
    for num in one_case:
        dist += math.sqrt((x_y[num][0] - x_prev)**2 + (x_y[num][1] - y_prev)**2)
        x_prev, y_prev = x_y[num][0], x_y[num][1]
print(dist / math.factorial(n))

Solution (Python):
import itertools
import math

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

distances = []
for root in itertools.permutations(range(1, n+1)):
    total = 0
    for i, j in enumerate(root):
        nxt_idx = (i+1) % len(root)
        nxt_root = root[nxt_idx]
        if nxt_idx == 0:
            break

        x1, y1 = roots[j-1]
        x2, y2 = roots[nxt_root-1]

        tmp = (x1 - x2)**2 + (y1-y2)**2
        distance = math.sqrt(tmp)
        total += distance

    distances.append(total)

ave = sum(distances) / len(distances)
print(ave)

Solution (Python):
import math
N = int(input())
p = []
d = []

def dfs(route, visited, n):
  total = 0
  if(len(route) == n + 1):
    for i in range(1, N):
      x1, y1 = d[route[i]]
      x2, y2 = d[route[i+1]]
      total += math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
      
    return total

  route.append(0)

  for i in range(n):
    if(visited[i]):
      continue

    route[-1] = i
    v = visited[::]
    v[i] = True
    total += dfs(route[::], v, n)
  
  return total

for i in range(N):
  d.append(list(map(int, input().split())))

a = 1

for i in range(1, N+1):
  a *= i

print(dfs([-1], [False] * N, N) / a)

Solution (Python):

import itertools
import numpy as np
import sys


def sr(): return sys.stdin.readline().rstrip()


def ir(): return int(sr())


def lr(): return list(map(int, sr().split()))


N = ir()

roots = []
for i in range(N):
    x, y = lr()
    roots.append([x, y])

ans = 0
path_dict = {}
all_path = list(itertools.permutations(range(0, N, 1)))
for pattern in all_path:
    sum_dist = 0
    for n1, n2 in zip(pattern, pattern[1:]):
        path = sorted([n1, n2])
        
        p1 = roots[path[0]]
        p2 = roots[path[1]]
        dist = np.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)
        
        
        

        sum_dist += dist
    ans += sum_dist
ans /= len(all_path)
print(ans)

Solution (Python):
import itertools
import math

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

ans=0
for perm in itertools.permutations(range(n)):
    l=0
    for j in range(n-1):
        l+=((x[perm[j+1]]-x[perm[j]])**2+(y[perm[j+1]]-y[perm[j]])**2)**0.5
    ans+=l
print(ans/math.factorial(n))

Solution (Python):
from itertools import permutations
from math import sqrt, factorial

N = int(input())
XY = [[int(i) for i in input().split()] for _ in range(N)]
sum = 0.0
for p in permutations(range(N), N):
    for i in range(N - 1):
        now = p[i]
        next = p[i + 1]
        dx = abs(XY[next][0] - XY[now][0])
        dy = abs(XY[next][1] - XY[now][1])
        sum += sqrt(dx * dx + dy * dy)
print(sum / factorial(N))

Solution (Python):
import math
import itertools

class Pos():
    def __init__(self, x, y):
        self.x = x
        self.y = y
    
def distance(a,b):
    return math.sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y))

points = []

num = int(input())
for i in range(num):
    x,y = input().split()
    points.append(Pos(int(x), int(y)))
    
total = 0
pattern = len(list(itertools.permutations(points)))

for l in itertools.permutations(points):
    n = len(l)
    for i in range(n-1):
        total = total + distance(l[i], l[i+1])
        
avg = total / pattern
print(avg)

Solution (Python):
from itertools import permutations
n = int(input())
plots = [0] * n
for i in range(n):
    x, y = map(int, input().split())
    plots[i] = (x, y)

roots = list(permutations(range(n)))
tmp = 0
for root in roots:
    for i in range(n-1):
        tmp += ((plots[root[i]][0] - plots[root[i + 1]][0]) ** 2 + (plots[root[i]][1] - plots[root[i + 1]][1]) ** 2) ** 0.5

print(tmp / len(roots))

Solution (Python):
import math
from itertools import combinations
 
N = int( input() )
 
def distance( a, b ):
  x1, y1 = a
  x2, y2 = b
  return math.sqrt( ( x1 - x2 ) ** 2 + ( y1 - y2 ) ** 2 )
 
d = []
for i in range(N):
  x, y = map( int, input().split() )
  d.append( [x, y] )
 
base = list(combinations(range(N),2))
sums = 0
for x in base:
  a, b = x
  sums += distance( d[a], d[b] )
print( sums / (len(base)) * ( N - 1 ))

Solution (Python):

from itertools import permutations

n=int(input())
xy=[[0]*2 for i in range(n)]
a=[0]*n
for i in range(n):
    xy[i]=list(map(int,input().split()))
    a[i]=i    

icnt=0
rsum=0
for i in permutations(a):
    icnt+=1
    r=0
    for ii in range(len(i)-1):
        j=i[ii]
        k=i[ii+1]
        r=r+((xy[k][0]-xy[j][0])**2+(xy[k][1]-xy[j][1])**2)**0.5
    rsum=rsum+r

print(rsum/icnt)

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

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

Solution (Python):
from itertools import combinations, permutations
from math import sqrt, factorial


def main():
    N = int(input())
    locations = list()
    for _ in range(N):
        x, y = list(map(int, input().split(' ')))
        locations.append((x, y))
    
    d = [[0 for _ in range(N)] for _ in range(N)]
    for edge in combinations(range(N), 2):
        from_town = edge[0]
        to_town = edge[1]
        from_x, from_y = locations[from_town]
        to_x, to_y = locations[to_town]
        d[from_town][to_town] = sqrt((from_x - to_x)**2 + (from_y - to_y)**2)
        d[to_town][from_town] = d[from_town][to_town]
    
    route_d_sum = 0
    for route in permutations(range(N), N):
        route_d = 0
        for i in range(N - 1):
            route_d += d[route[i]][route[i + 1]]
        route_d_sum += route_d
    
    print(route_d_sum / factorial(N))


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import permutations
from math import sqrt
n = int(input())
x = [0] * n
y = [0] * n
for i in range(n):
    x[i], y[i] = map(int, input().split())

p = [i for i in range(n)]
c = 0
d = 0.0
dp = [[0.0 for _ in range(n)] for _ in range(n)]
for a in permutations(p):
    c += 1
    for i in range(n - 1):
        if dp[a[i]][a[i + 1]] == 0.0:
            dp[a[i]][a[i + 1]] = sqrt((x[a[i]] - x[a[i + 1]]) ** 2 + (y[a[i]] - y[a[i + 1]]) ** 2)
            dp[a[i + 1]][a[i]] = dp[a[i]][a[i + 1]]
        d += dp[a[i]][a[i + 1]]
print("{:10f}".format(d / c))

Solution (Python):
from itertools import permutations
from math import sqrt
n = int(input())
x = [0] * n
y = [0] * n
for i in range(n):
    x[i], y[i] = map(int, input().split())

p = [i for i in range(n)]
c = 0
d = 0.0
dp = [[0.0 for _ in range(n)] for _ in range(n)]
for a in permutations(p):
    c += 1
    for i in range(n - 1):
        if dp[a[i]][a[i + 1]] == 0.0:
            dp[a[i]][a[i + 1]] = sqrt((x[a[i]] - x[a[i + 1]]) ** 2 + (y[a[i]] - y[a[i + 1]]) ** 2)
        d += dp[a[i]][a[i + 1]]
print("{:10f}".format(d / c))

Solution (Python):
from itertools import permutations
from math import sqrt
n = int(input())
x = [0] * n
y = [0] * n
for i in range(n):
    x[i], y[i] = map(int, input().split())

p = [i for i in range(n)]
c = 0
d = 0.0
for a in permutations(p):
    c += 1
    for i in range(n - 1):
        d += sqrt((x[a[i]] - x[a[i + 1]]) ** 2 + (y[a[i]] - y[a[i + 1]]) ** 2)
print("{:10f}".format(d / c))

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

ans = 0
for i in itertools.permutations(range(n), n):
    tmp = i[0]
    for j in i:
        ans += (((xy[tmp][0]-xy[j][0])**2 + (xy[tmp][1]-xy[j][1])**2)**0.5)
        tmp = j
print(ans/math.factorial(n))

Solution (Python):
import itertools
from math import sqrt
N = int(input())
POINTS = []
for n in range(N):
    x,y = list(map(int,input().split()))
    POINTS.append({"x":x,"y":y})

ans = 0
num=0
for candidate in itertools.permutations(POINTS):
    num +=1
    for i,v in enumerate(candidate):
        if i == 0:
            continue
        prev = candidate[i-1]
        ans += sqrt((v["x"] - prev["x"]) ** 2 +(v["y"]-prev["y"]) ** 2)
print(str(ans/num))