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 math

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


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


route = 0
for i in range(N):
    for j in range(i + 1, N):
        route+=dist(x[i], y[i], x[j], y[j])
ave = (route * (2 * math.factorial(N - 1))) / math.factorial(N)
print(ave)

Solution (Python):
import math
import itertools

n = int(input())
x, y = [0]*n, [0]*n
for i in range(n):
    a, b = map(int, input().split())
    x[i], y[i] = a, b
l = list(itertools.permutations(range(n)))

tmp = 0
for p in l:
    for j in range(n-1):
        a = p[j]
        b = p[j+1]
        tmp += math.sqrt((x[a]-x[b])**2 + (y[a]-y[b])**2)

print(round(tmp/len(l), 10))

Solution (Python):
import itertools
import sys
import math
input = sys.stdin.readline

N = int(input())
x = []
y = []

for i in range(N):
    p, q = map(int, input().split())
    x.append(p)
    y.append(q)

ans = 0
j = 0
num_old = 0

lis = [x for x in range(N)] 
permutations_lis = itertools.permutations(lis)

for one_case in permutations_lis:
    i = 0
    j += 1
    for num in one_case:

        if i != 0:
            ans += math.sqrt((x[int(num_old)]-x[int(num)])**2+(y[int(num_old)]-y[int(num)])**2)

        i += 1
        num_old = num



ans = ans / j
print (ans)

Solution (Python):
import sys
import math
input = sys.stdin.readline

N = int(input())
x = []
y = []

for i in range(N):
    p, q = map(int, input().split())
    x.append(p)
    y.append(q)

ans = 0

for i in range(N):
    for j in range(N):
        if i == j:
            continue



        ans += math.sqrt((x[i]-x[j])**2+(y[i]-y[j])**2)

ans = ans / N
print (ans)

Solution (Python):
import numpy as np 
import itertools
N = int(input())
pos = []
for _ in range(N):
    pos.append(list(map(int,input().split())))
pos = np.array(pos)

dist_dict = {}
def dist(n0,n1): 
    k = str(min(n0,n1))+str(max(n0,n1))
    if k in dist_dict:
        d = dist_dict[k]
    else:
        d = np.sqrt(np.sum(np.power(pos[n1]-pos[n0],2)))
        dist_dict[k] =d
    return d

pattern_list = list(itertools.permutations(range(N))) 
ans = 0
for pattern in pattern_list:
    pre_node = pattern[0]
    for i in range(1,N):
        next_node = pattern[i]
        ans+=dist(pre_node,next_node)
        pre_node = next_node

for i in range(1,N+1):
    ans /= i

print(ans)

Solution (Python):
import sys
from itertools import permutations
from math import factorial
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

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

dist = 0
for route in permutations(XY, N):
    acc = 0
    dists = [
        pow(
            pow(route[i][0] - route[i + 1][0], 2) +
            pow(route[i][1] - route[i + 1][1], 2), .5) for i in range(N - 1)
    ]
    dist += sum(dists)
print(dist / factorial(N))

Solution (Python):
import sys
from itertools import permutations
from math import factorial
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

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

dist = 0
for route in permutations(XY, N):
    acc = 0
    dists = [
        np.sqrt(
            pow(route[i][0] - route[i + 1][0], 2) +
            pow(route[i][1] - route[i + 1][1], 2)) for i in range(N - 1)
    ]
    dist += sum(dists)
print(dist / factorial(N))

Solution (Python):
n = int(input())
town = [list(map(int,input().split())) for _ in range(n)]
ans = 0
def dist(a,b,c,d):
	return ((a-c)**2+(b-d)**2)**0.5
for i in range(n):
	for j in range(n):
		ans += dist(town[i][0],town[i][1],town[j][0],town[j][1])
print(ans/(n))

Solution (Python):
import itertools
import math
N = int(input())
cities = []
indexes = []
for i in range(N):
    cities.append(list(map(int, input().split())))
    indexes.append(i)


indexes_permutaions = list(itertools.permutations(indexes))
costs = []
for indexes_permutaion in indexes_permutaions:
    cost = 0
    for i in range(len(indexes_permutaion) - 1):
        index = indexes_permutaion[i]
        next_index = indexes_permutaion[i + 1]
        num = math.sqrt((((cities[next_index][0] - cities[index][0])
                          ** 2) + ((cities[next_index][1] - cities[index][1]) ** 2)))
        cost += num
    costs.append(cost)
print(float(sum(costs)) / len(costs))

Solution (Python):
import itertools
import math


def dist(a, b):
    return math.sqrt((a[0] - b[0])**2 + (a[1] - b[1])**2)


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

s = 0
for cmb in itertools.combinations(C, 2):
    s += 2 * dist(cmb[0], cmb[1]) / N

print(s)

Solution (Python):
import itertools
import math


def dist(a, b):
    return math.sqrt((a[0] - b[0])**2 + (a[1] - b[1])**2)


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

s = 0
for per in itertools.permutations(C):
    for i in range(N-1):
        s += dist(per[i], per[i+1])

print(s / len(list(itertools.permutations(C))))

Solution (Python):
import math
N=int(input())
X=[0.0]*N
Y=[0.0]*N
S=0.0
for i in range(N):
    X[i],Y[i]=map(int,input().split())

for j in range(N-1):
    for k in range(j+1,N):
        S+=math.sqrt((X[j]-X[k])**2+(Y[j]-Y[k])**2)
        
print(round(S*2/N,10))

Solution (Python):
N=int(input())
point=[list(map(int,input().split())) for i in range(N)]
distance=0
for i in range(N-1):
    for j in range(i+1,N):
        try:
            a,b=tuple(point[i])
            c,d=tuple(point[j])
            a-=c
            b-=d
            distance+=(a**2+b**2)**(1/2)
        except:
            continue
print(2*distance/N)

Solution (Python):
import math
import itertools

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


min_load_map = []
for i in range(N):
  arr = []
  for t in range(N):
    min_i_to_t = math.sqrt((a[i][0] - a[t][0])**2 + (a[i][1] - a[t][1])**2)
    arr.append(min_i_to_t)
  min_load_map.append(arr)

ans = float()


patterns = itertools.permutations(range(N))
count = 0
for pat in patterns:
  count += 1
  pat = list(pat)
  tmp = 0
  for p in range(1, len(pat)):
    tmp += min_load_map[pat[p-1]][pat[p]]
  ans += tmp

ans /=  count
  
print(ans)

Solution (Python):
N = int(input())
xy = []
for i in range(N):
    a, b = (int(x) for x in input().split())
    xy.append([a, b])
    
def distance(d, xy, i, j):
    return (
              (xy[i][0] - xy[j][0]) ** 2
            + (xy[i][1] - xy[j][1]) ** 2
        ) ** 0.5
 
import itertools
d = []
l1 = [x for x in range(N)]
for v in itertools.permutations(l1, N):
    l2 = list(v)
    d0 = []
    for c in range(N-1):
        i = l2[c]
        j = l2[c+1]
        d0.append(distance(d, xy, i, j))
    d.append(sum(d0))
 
print(sum(d) / len(d))

Solution (Python):
import itertools
n=int(input())

x,y=[],[]
for _ in range(n):
    a,b=map(int,input().split())
    x.append(a)
    y.append(b)
l=list(itertools.permutations(range(n)))
 
wrk=0
for p in l:
    for j in range(0,n-1):
        a=p[j]
        b=p[j+1]
        wrk+=((x[a]-x[b])**2+(y[a]-y[b])**2)**0.5
print(wrk/len(l))

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

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

for i in range(n):
   for j in range(i+1, n):
      d = ((town[i][0]-town[j][0])**2+(town[i][1]-town[j][1])**2)**0.5
      dist[i][j] = d
      dist[j][i] = d

dist2 = [sum(x) for x in dist]
print(sum(dist2)/n)

Solution (Python):
import itertools
n=int(input())

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

l=list(itertools.permutations(range(n)))

a=0
for p in l:
    for j in range(0,n-1):
        a+=((x[p[j]]-x[p[j+1]])**2+(y[p[j]]-y[p[j+1]])**2)**0.5
print(a/len(l))

Solution (Python):
from itertools import permutations
n=int(input())
x=[0]*n
y=[0]*n
for i in range(n):
  x[i],y[i]=map(int,input().split())
a=0
for p in permutations([i for i in range(n)]):
  for j in range(1,n):
    a+=((x[p[j]]-x[p[j-1]])**2+(y[p[j]]-y[p[j-1]])**2)**0.5
for i in range(1,n+1):
  a/=i
print(a)

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

perm_towns = list(itertools.permutations(towns))
sum_length = 0
for i in range(len(perm_towns)):
    for j in range(n-1):
        length = ((perm_towns[i][j][0]-perm_towns[i][j+1][0]) **2 + (perm_towns[i][j][1] - perm_towns[i][j+1][1]) **2) **0.5
        sum_length += length 

ans = sum_length / (len(perm_towns))
print(ans)

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

city = []
for _ in range(N):
    x, y = map(int,input().split(" "))
    city.append((x,y))
    
ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        x1, y1 = city[i]
        x2, y2 = city[j]
        
        ans += ( ( (x2-x1)**2 + (y2-y1)**2 )**0.5 )*(2/N)
        
print(ans)

Solution (Python):
import numpy as np
n = int(input())
towns = []
for _ in range(n):
    x,y = map(int,input().split())
    towns.append((x,y))
dist = []
for i in range(n-1):
    for j in range(i+1,n):
        x1,y1 = towns[i]
        x2,y2 = towns[j]
        dist.append(np.sqrt((x1-x2)**2+(y1-y2)**2))
print((sum(dist)/len(dist)) * (n-1))

Solution (Python):
import numpy as np
n = int(input())
towns = []
for _ in range(n):
    x,y = map(int,input().split())
    towns.append((x,y))
dist = []
for i in range(n-1):
    for j in range(i+1,n):
        x1,y1 = towns[i]
        x2,y2 = towns[j]
        dist.append(np.sqrt((x1-x2)**2+(y1-y2)**2))
print((sum(dist)/len(dist)) * (n-1))

Solution (Python):
from sys import stdin
import itertools
import math

n = int(stdin.readline().rstrip())
l = [int(x) for x in range(n)]
p = itertools.permutations(l, n)

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

total = 0
for i in p:
    for j in range(n - 1):
        p1 = i[j] - 1
        p2 = i[j + 1] - 1
        dis = math.sqrt((xy[p2][0] - xy[p1][0])**2 +
                        (xy[p2][1] - xy[p1][1])**2)
        total += dis

print(total/math.factorial(n))

Solution (Python):
def main():
  import sys
  input = sys.stdin.readline
  n=int(input())
  xy=[list(map(int,input().split())) for _ in [0]*n]
  ans=0
  for i in range(n):
    xi,yi=xy[i][0],xy[i][1]
    for j in range(i+1,n):
      xj,yj=xy[j][0],xy[j][1]
      ans+=pow(pow(xi-xj,2)+pow(yi-yj,2),0.5)
  print(ans*2/n)
  
if __name__ == '__main__':
    main()

Solution (Python):
def main():
  import sys
  input = sys.stdin.readline
  n=int(input())
  xy=[list(map(int,input().split())) for _ in [0]*n]
  ans=0
  for i in range(n):
    xi,yi=xy[i][0],xy[i][1]
    for j in range(n):
      xj,yj=xy[j][0],xy[j][1]
      ans+=pow(pow(xi-xj,2)+pow(yi-yj,2),0.5)
  print(ans/n)
if __name__ == '__main__':
    main()

Solution (Python):
def main():
  import sys
  input = sys.stdin.readline
  import math 
  import itertools 
  n=int(input())
  xy=[list(map(int,input().split())) for _ in [0]*n]
  l=''.join([str(i) for i in range(n)])
  sum=0
  for i in itertools.permutations(l):
    i=''.join(list(i))
    for j in range(n-1):
      a,b=int(i[j+1]),int(i[j])
      sum+=pow(pow(xy[a][0]-xy[b][0],2)+pow(xy[a][1]-xy[b][1],2),0.5)
  m=math.factorial(n)
  print(sum/m)
if __name__ == '__main__':
    main()

Solution (Python):
import itertools

N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
l = [i for i in range(N)]
pl = itertools.permutations(l)
d = 0
cnt = 0

for one_case in pl:
  cnt += 1
  for i in range(N - 1):
    a = one_case[i]
    b = one_case[i + 1]
    dx = (xy[a][0] - xy[b][0])**2
    dy = (xy[a][1] - xy[b][1])**2
    d += (dx + dy)**0.5
    
print(d / cnt)

Solution (Python):
import sys

import numpy as np
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
"""dd = [(-1, 0), (0, 1), (1, 0), (0, -1)];
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)];
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""

def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]  
def grid(n): return [s_list() for _ in range(n)]


def main():

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

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

    p = list(itertools.permutations(number))
    d = 0.0
    for p_1 in p:
        for i in range(n-1):
            p_1 = list(p_1)

            d += np.sqrt((xy[p_1[i]][0] - xy[p_1[i+1]][0])**2 + (xy[p_1[i]][1] - xy[p_1[i+1]][1])**2)
    ans = d/len(p)
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
XY=[list(map(int,input().split())) for _ in range(n)]
ans=0
N=0
tmp=0
from itertools import permutations
from math import hypot 
for i in permutations(XY):
  N+=1
  for (x,y),(x1,y1) in zip(i,i[1:]):
    tmp+=hypot(x-x1,y-y1)

print(tmp/N)

Solution (Python):
from itertools import permutations
n=int(input())
l=[]
for i in range(n):
    x,y=map(int,input().split())
    l.append((x,y))
dist=[]
for ll in list(permutations(l)):
    d=0.0
    for i in range(len(ll)-1):
        d+=((ll[i][0]-ll[i+1][0])**2+(ll[i][1]-ll[i+1][1])**2)**0.5
    dist.append(d)
print(sum(dist)/len(dist))

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
x = []
y = []
for i in range(N) :
    p, q = map(int,input().split())
    x.append(p)
    y.append(q)

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

ans = ans / N
print(ans)

Solution (Python):
from math import factorial

n = int(input())

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

def dist(a, b):
    return ((pos[a][0] - pos[b][0]) ** 2 + (pos[a][1] - pos[b][1]) ** 2) ** (1/2)

ans = 0
def calc(status, total, prev):
    global ans
    if status == (1<<n) - 1:
        ans += total
        return
    for i in range(n):
        if status>>i&1:
            continue
        else:
            calc(status|(1<<i), total + dist(prev, i), i)

for i in range(n):
    calc(1<<i, 0, i)

print('{:.6f}'.format(ans/factorial(n)))

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

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

dist = [[] for i in range(n)]
s = 0
for i, (x, y) in enumerate(c):
    for x0, y0 in c:
        s += ((x0-x)**2 + (y0-y)**2)**0.5



print(s / n)

Solution (Python):
n = int(input())
length = 0
x = []
y = []
for i in range(n):
    xi,yi = map(int,input().split())
    x.append(xi)
    y.append(yi)
for i in range(n):
    for k in range(n):
        length += ((x[i]-x[k])**2+(y[i]-y[k])**2)**0.5
print(length/n)

Solution (Python):
from itertools import combinations

n = int(input())

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


def length(list1, list2):
    return ((list1[0] - list2[0])**2 + (list1[1] - list2[1])**2) ** 0.5

ans = 0

for a, b in combinations(places, 2):
    
    ans += length(a, b)

print(ans * 2 / n)

Solution (Python):
import itertools
import math 

N = int(input())
coordList = []
permList = []
distList = []
distance = 0

for i in range(N):
  x = input().split()
  coordList.append(x)

permList = list(itertools.permutations(coordList))

for perm in range(len(permList)):
  xList = []
  yList = []
  
  for coord in range(len(permList[perm])):
    for num in range(len(permList[perm][coord])):
      if len(xList) != N and num + 1 < 2:
        xList.append(int(permList[perm][coord][num]))
        
      if len(yList) != N and num + 1 < 2:
        yList.append(int(permList[perm][coord][num + 1]))
        
      elif len(xList) and len(yList) == N: 
        for i in range(N):
          if i + 1 < N: 
            dist = math.sqrt(((xList[i] - xList[i+1]) ** 2) + ((yList[i] - yList[i+1]) ** 2))
            distList.append(dist)

for i in range(len(distList)):
  distance += distList[i]

print(distance / math.factorial(N))

Solution (Python):
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
import itertools as it
ans=0
for i in it.permutations(range(n),n):
    x=xy[i[0]][0]
    y=xy[i[0]][1]
    for k in range(1,n):
        j=i[k]
        ans+=((x-xy[j][0])**2+(y-xy[j][1])**2)**0.5
        x=xy[j][0]
        y=xy[j][1]
N=1
for i in range(1,n+1):
    N*=i
print(ans/N)

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

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

fact = [1]
for i in range(1, n + 1):
    fact.append(fact[-1] * i)

sm = 0
for pat in permutations(range(n), n):
    for e1, e2 in zip(pat, pat[1:]):
        x1, y1 = xy[e1]
        x2, y2 = xy[e2]
        dist = sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
        sm += dist

ans = sm / fact[n]
print(ans)

Solution (Python):
import itertools
import math
n=int(input())
data=[]
a=[]
for i in range(n):
    x,y=map(int,input().split())
    data.append([x,y])
    a.append(i)
d=0.0
for v in itertools.permutations(a):
    for i in range(n-1):
        d0=((data[v[i]][0]-data[v[i+1]][0])**2+(data[v[i]][1]-data[v[i+1]][1])**2)**0.5
        d+=d0
print(d/math.factorial(n))

Solution (Python):
import math
import itertools

N = int(input())

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

perm_C = itertools.permutations(Cities)

total = 0
count = 0
for route in perm_C:
  count += 1
  current = route[0]
  distance_sum = 0
  for city in route[1:]:
    distance = math.sqrt(pow(current[0]-city[0], 2) + pow(current[1]-city[1], 2))
    distance_sum += distance
  total += distance_sum

avg = total / count
print("{:.7f}".format(avg))

Solution (Python):

import math

n = int(input().rstrip())


class Pos:
    def __init__(self, init: list):
        self.x = init[0]
        self.y = init[1]

    def get_dist(self, target):
        return math.sqrt(pow(target.x - self.x, 2) + pow(target.y - self.y, 2))


mati_list = [Pos([int(i) for i in input().rstrip().split(" ")]) for j in range(n)]


def get_kumiawase(prev: int, flag: list):
    if len([i for i in flag if i == False]) == 0:
        return [0]
    ans = []
    for i in range(n):
        if flag[i]:
            continue
        diff = mati_list[prev].get_dist(mati_list[i])
        flag[i] = True
        ret = get_kumiawase(i, flag)
        flag[i] = False
        for j in ret:
            ans.append(j + diff)
    return ans


kumiawase = []
for i in range(n):
    ret = get_kumiawase(i, [j == i for j in range(n)])
    kumiawase += ret

print(sum(kumiawase) / len(kumiawase))

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

def permutations(nums, path, p):
    if len(nums) == 0:
        p.append(path)
        return
    for i in range(len(nums)):
        permutations(nums[:i] + nums[i + 1:], path + [nums[i]], p)

p = []
permutations([i for i in range(n)], [], p)

average = 0
for way in p:
    length = 0
    for i in range(len(way) - 1):
        start = way[i]
        end = way[i + 1]
        length += ((xy[start][0] - xy[end][0]) ** 2 + (xy[start][1] - xy[end][1]) ** 2) ** 0.5
    average += length / len(p)
print(average)

Solution (Python):
def dis(a, b):
    return np.sqrt((a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1]))
import itertools
import numpy as np
n = int(input())
coor = []
for _ in range(n):
    x, y = map(int, input().split())
    coor.append([x,y])

permutations_lis = itertools.permutations(range(n))
dis_list = []
for case in permutations_lis:
    dis_sum = 0
    for i in range(n-1):
        dis_sum += dis(coor[case[i]], coor[case[i+1]])
    dis_list.append(dis_sum)

print(np.mean(dis_list))

Solution (Python):
import numpy as np
N=int(input())
xy=np.array([list(map(int,input().split())) for i in range(N)])
print(sum(np.linalg.norm(i-j) for i in xy for j in xy)/N)

Solution (Python):
N=int(input())
xy=[list(map(int,input().split())) for i in range(N)]
print(sum(((xi-xj)**2+(yi-yj)**2)**.5 for xi,yi in xy for xj,yj in xy)/N)

Solution (Python):
N=int(input())
xy=[list(map(int,input().split())) for i in range(N)]
distance=0
for xi,yi in xy:
    for xj,yj in xy:
        distance+=((xi-xj)**2+(yi-yj)**2)**.5
print(distance/N)

Solution (Python):
import itertools
import math

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

for route in itertools.permutations(range(n)):
    prev = coordinate[route[0]]
    for i in range(1, n):
        ans += math.sqrt((prev[0] - coordinate[route[i]][0])**2 + (prev[1] - coordinate[route[i]][1])**2)
        prev = coordinate[route[i]]

print(ans / math.factorial(n))

Solution (Python):
import math
from itertools import permutations
n = int(input())
xy = [[int(i) for i in input().split()] for _ in range(n)]
arr = list(permutations(range(n), n))
ans = 0
for i in range(len(arr)):
    for j in range(1, n):
        ans += math.sqrt(pow(xy[arr[i][j]][0] - xy[arr[i][j-1]][0], 2) + pow(xy[arr[i][j]][1] - xy[arr[i][j-1]][1], 2))
ans /= len(arr)
print(ans)

Solution (Python):
def main():
    import sys
    
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from math import floor, ceil
    

    

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

if __name__ == '__main__':
    main()

Solution (Python):
'''
https://atcoder.jp/contests/abc145/tasks/abc145_c
'''
def main():
    import sys
    
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from math import floor, ceil
    

    

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


if __name__ == '__main__':
    main()

Solution (Python):
'''
https://atcoder.jp/contests/abc145/tasks/abc145_c
'''
def main():
    import sys
    
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from math import floor, ceil
    

    

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


if __name__ == '__main__':
    main()

Solution (Python):
import itertools
import math

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

nums = [_ for _ in range(n)]
total = 0
for v in itertools.permutations(nums, n):
    dist = 0
    for i in range(n-1):
        dist += math.sqrt((dots[v[i]][0] - dots[v[i+1]][0]) **
                          2 + (dots[v[i]][1] - dots[v[i+1]][1])**2)
    total += dist

print(total/math.factorial(n))

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

Solution (Python):
import sys,math,itertools
import numpy as np

n=int(sys.stdin.readline())
a=np.array([sys.stdin.readline().split() for _ in range(n)],dtype='int64')

to=0
num=0
b=np.zeros((n,n))

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


for i in itertools.permutations(range(n)):
    f=0
    num+=1
    for j in i:
        if f==0:
            c=j
            f=1
        else:
            if c>j:
                to+=b[j,c]
            else:
                to+=b[c,j]
            c=j


print(to/num)

Solution (Python):
from itertools import combinations
import math

n = int(input())

towns = []

for _ in range(n):
    array = list(map(int, input().split()))
    towns.append(array)


distances = [[0 for _ in range(n)] for _ in range(n)]

town_num = list(range(n))

for i, j in combinations(town_num, 2):
    distance = ((towns[j][0] - towns[i][0])**2 + (towns[j][1] - towns[i][1])**2)**(0.5)
    distances[i][j] = distance
    distances[j][i] = distance

total_way = math.factorial(n)

total = 0

for i in range(n):
    for j in range(n):
        total += distances[i][j] * math.factorial(n-1)

print(total/total_way)

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


s = sum(sqrt((xy[i][0] - xy[j][0])**2 + (xy[i][1] - xy[j][1])**2) for i,j in comb(range(n), 2))
print(s * 2 / n)

Solution (Python):
from itertools import permutations

N = int(input())
lx, ly = [], []
for _ in range(N):
    xi, yi = list(map(int, input().split()))
    lx.append(xi)
    ly.append(yi)

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

mcost = 0
for x in permutations(list(range(N))):
    cost = 0.0
    for i in range(len(x) - 1):
        dij = ((lx[x[i]] - lx[x[i + 1]]) ** 2 + (ly[x[i]] - ly[x[i + 1]]) ** 2) ** 0.5
        cost += dij
    mcost += cost / fN
print(mcost)

Solution (Python):
import itertools
import math

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

ans = 0
for p in itertools.permutations(list(range(n))):
    for i in range(1, n):
        s, t = p[i-1], p[i]
        ans += ((x[s]-x[t])**2 + (y[s]-y[t])**2)**0.5

print(ans/math.factorial(n))

Solution (Python):


import itertools


def main():
    N = int(input())
    XY = [list(map(int, input().split())) for _ in range(N)]
    roots = list(itertools.permutations(XY))

    cnt, result = len(roots), 0
    
    for root in roots:
        for i in range(len(root) - 1):
            result += ((root[i][0] - root[i + 1][0])**2 +
                       (root[i][1] - root[i + 1][1])**2)**0.5
    print(result / cnt)


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
l=[]
for i in range(n):
        tmp = list(map(int,input().split()))
        l.append(tmp)
lis = range(n)
import itertools
import math
cities = list(itertools.permutations(lis))
ans=0
for j in range(len(cities)):
        vils = cities[j]
        for i in range(1,n):
                last= l[vils[i-1]]
                now = l[vils[i]]
                dist = (last[0] - now[0])**2 + (last[1] - now[1])**2
                dist = math.sqrt(dist)
                ans+=dist
print(ans/len(cities))

Solution (Python):
import math
N=int(input())
point=[list(map(int,input().split())) for _ in range(N)]
l=[i+1 for i in range(N)]
dist1=0
dist=[]
for i in range(0,N,1):
    for j in range(i+1,N,1):
        dist1=dist1+math.sqrt(pow(point[i][0]-point[j][0],2)+pow(point[i][1]-point[j][1],2))
print(dist1*2*(N-1)/(N*(N-1)))

Solution (Python):
import itertools
import math

N = int(input())
coodinate_list = [tuple(map(int, input().split(' '))) for _ in range(N)]
idx_list = [x for x in range(N)]
idx_permutations = itertools.permutations(idx_list)

total_dist = 0
permutaions_len = 0
for one_case in idx_permutations:
    permutaions_len += 1
    dist = 0
    for idx in range(len(one_case)):
        if idx > 0:
            dist += math.sqrt(math.pow(coodinate_list[one_case[idx]][0]-coodinate_list[one_case[idx-1]][0], 2)+math.pow(coodinate_list[one_case[idx]][1]-coodinate_list[one_case[idx-1]][1], 2))
    total_dist += dist
print(total_dist / permutaions_len)