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, math

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

routes = itertools.permutations(shops, N)
l = list(routes)

total = 0
for route in l:
    tmp = 0
    for i in range(1,len(route)):
        kyori = (route[i][0]-route[i-1][0])**2 + (route[i][1]-route[i-1][1])**2
        tmp += math.sqrt(kyori)
    total += tmp
ans = total/len(l)
print(ans)

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

Solution (Python):
from itertools import permutations

def solve():
    N = int(input())
    A = []
    for _ in range(N):
        a, b = list(map(int, input().split()))
        A.append([a, b])
    l = list(permutations(A))
    s = 0
    for t in l:
        for i in range(N-1):
            a, b = t[i]
            c, d = t[i+1]
            s = s + ((a-c)**2 + (b-d)**2) ** 0.5
    return s / len(l)

print(solve())

Solution (Python):
n = int(input())
L = []
for i in range(n):
    a,b = map(int,input().split())
    L.append([a,b])
import itertools
def dis(p,q,r,s):
    return ((p-r)**2 + (q-s)**2)**0.5
ans = 0
cnt1 = 0
for v in itertools.permutations(L):
    cnt1 +=1
    for i in range(n-1):
        ans +=dis(v[i][0],v[i][1],v[i+1][0],v[i+1][1])
print(ans/cnt1)

Solution (Python):

import math
import itertools
n=int(input())
zahyo=[]
for i in range(n):
    line=list(map(int,input().split()))
    zahyo.append(line)
num=[i for i in range(n)]
patarn=list(itertools.permutations(num))


def siwu(x,keta):
    x=x*10**keta
    if (x*10)%10>=5:
        x+=1
    x=int(x)
    x/=10**keta
    return x


def kyori(xy1,xy2):
    x1,y1=xy1
    x2,y2=xy2
    s=math.sqrt((x1-x2)**2+(y1-y2)**2)
    return s
ans=0
for i in patarn:
    s=0
    for j in range(n-1):
        s+=kyori(zahyo[i[j]],zahyo[i[j+1]])
    ans+=s
ans/=len(patarn)

print(ans)

Solution (Python):
import itertools
import math

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

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

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

distsum = 0
for i in range(len(Pt)):
    for j in range(N-1):
        distsum += dist(C[Pt[i][j]][0],C[Pt[i][j]][1],C[Pt[i][j+1]][0],C[Pt[i][j+1]][1])

print(distsum / len(Pt))

Solution (Python):
from itertools import permutations
import statistics

N = int(input())
box = [list(map(int, input().split())) for _ in range(N)]
p_box = permutations(box)
ans = []
for i in p_box:
    temp = 0
    for j in range(1, N):
        temp += ((i[j][0] - i[j-1][0])**2 + (i[j][1] - i[j-1][1])**2)**(1/2)
    ans.append(temp)

print(statistics.mean(ans))

Solution (Python):
import itertools
import math

N = int(input())
nums = [i for i in range(N)]
town = []
distance = {}
d_sum = 0

for _ in range(N):
    town.append(list(map(int, input().split())))
    
for i in range(N):
    for j in range(i + 1, N):
        key = str(i) + "_" + str(j)
        distance[key] = (math.sqrt((town[i][0] - town[j][0]) ** 2 + (town[i][1] - town[j][1]) ** 2 ))

for v in itertools.permutations(nums, N):
    for i in range(N -1):
        if v[i] > v[i + 1]:
            key = str(v[i + 1]) + "_" + str(v[i])
        else:
             key = str(v[i]) + "_" + str(v[i + 1])
        d_sum += distance[key]

print(d_sum / math.factorial(N))

Solution (Python):
import itertools
import math
n = int(input())
l = list(itertools.permutations(range(n)))
X = []
Y = []
for i in range(n):
  x,y = map(int,input().split())
  X.append(x)
  Y.append(y)
result = []
for i in l:
  
  d = 0
  for j in range(int(len(i))-1):
    d += math.sqrt((X[i[j]]-X[i[j+1]])**2 + (Y[i[j]]-Y[i[j+1]])**2)
    
  result.append(d)
print(sum(result)/len(result))

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

Solution (Python):
import math
import itertools

N = int(input())
x= [0]*N
y= [0]*N
for i in range(N):
  x[i], y[i] = map(int, input().split())
D = [[0]*N for i in range(N)]
for i in range(N):
  for j in range(N):
    D[i][j] = ((x[i]-x[j])**2+(y[i]-y[j])**2)**0.5
P = list(itertools.permutations(list(range(N)),N))
dist = [0]*len(P)
for j, p in enumerate(P):
  for i in range(N-1):
    dist[j] += D[p[i]][p[i+1]]
ave = sum(dist)/len(P)
print(ave)

Solution (Python):
import itertools
import math
n = int(input())
x_y = [list(map(int, input().split())) for _ in range(n)]
ans = 0
perm = itertools.permutations(range(n))
for p in perm:
    for i in range(n - 1):
        pos = p[i]
        next_pos = p[i + 1]
        ans += ((x_y[pos][0] - x_y[next_pos][0]) ** 2 + (x_y[pos][1] - x_y[next_pos][1]) ** 2) ** (1/2)
print(ans / math.factorial(n))

Solution (Python):
import itertools
from math import sqrt
def main():
    def helper():
        pass
    def dist(p1, p2):
        dX, dY = p1[0]-p2[0], p1[1]-p2[1]
        return sqrt(dX*dX+dY*dY)

    N = int(input())
    P = []
    for _ in range(N):
        x, y = map(int, input().split())
        P.append((x, y))
    
    D = []
    ct = 0
    for p_list in itertools.permutations(P, N):
        ct += 1
        d = 0
        for i in range(len(p_list)-1):
            d += dist(p_list[i], p_list[i+1])
        D.append(d)
    print(sum(D)/ct)

main()

Solution (Python):
def dist(x, y):
    return ((x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2) ** .5

N = int(input())
lst = []
for _ in range(N):
    lst.append([int(x) for x in input().split()])

d = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        d += dist(lst[i], lst[j])

print(d * 2 / N)

Solution (Python):

"""
Created on Tue Mar 10 20:52:06 2020

@author: Kanaru Sato
"""
import math

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

sum_d = 0

for i in range(0,n):
    for j in range(0,n):
        d_sq = (cities[i][0]-cities[j][0])**2+(cities[i][1]-cities[j][1])**2
        sum_d = sum_d + math.sqrt(d_sq)

print(sum_d/n)

Solution (Python):
import math
import itertools

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

arr = list(range(n))
p = list(itertools.permutations(arr))

def calc(x1,y1,x2,y2):
    return ((x1-x2) ** 2 + (y1-y2) ** 2) ** 0.5

ans = []

for p_arr in p:
    s = 0.0
    for i in range(1,len(p_arr)):
        s += calc(x[p_arr[i]],y[p_arr[i]],x[p_arr[i-1]],y[p_arr[i-1]])
    ans.append(s)

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

Solution (Python):
from itertools import permutations
import math

n = int(input())
arr = [tuple(map(int, input().split())) for _ in range(n)]
total = 0
for v in permutations(arr, n):
    d = 0
    for i in range(n-1):
        x1, y1 = v[i]
        x2, y2 = v[i+1]
        d += math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
    total += d
print(total / math.factorial(n))

Solution (Python):
import itertools as it
n = int(input())
zahyou = []
for i in range(n):
    x,y = map(int, input().split())
    zahyou.append((x,y))
perm = list(it.permutations(range(n),n))
ans = 0
for zyu in perm:
    for i in range(n-1):
        ans += ((zahyou[zyu[i]][0] - zahyou[zyu[i+1]][0])**2 +(zahyou[zyu[i]][1] - zahyou[zyu[i+1]][1])**2 )**.5
ans /=len(perm)
print(ans)

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

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

def sumdis(m):
  res = 0
  for i in range(0,n-1):
    for j in range(i+1,n):
      res += dis(m[i], m[j])
  return res*2/n

print(sumdis(List))

Solution (Python):
import math
import itertools

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

P = itertools.permutations(range(N))
ans = []
for p in P:
    s = 0
    for i in range(len(p) - 1):
        s += math.sqrt(
            math.pow(c[p[i]][0] - c[p[i + 1]][0], 2)
            + math.pow(c[p[i]][1] - c[p[i + 1]][1], 2)
        )
    ans.append(s)

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

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    xy = [tuple(map(int, input().split())) for _ in range(N)]
    def dist(xy1,xy2): return ((xy1[0]-xy2[0])**2 + (xy1[1]-xy2[1])**2)**0.5
    ans = 0
    for i in range(N):
        for j in range(i+1,N):
            ans += dist(xy[i],xy[j])
    print(ans*2/N)

if __name__ == '__main__':
    main()

Solution (Python):
from itertools import permutations

n = int(input())
x, y = zip(*[list(map(int, input().split()))for i in range(n)])
ans = cnt = 0
for i in permutations(range(n)):
        cnt += 1
        for j in range(n-1):
                f, t = i[j], i[j+1]
                ans += ((x[f]-x[t])**2 + (y[f]-y[t])**2)**0.5
print(ans/cnt)

Solution (Python):
def fact(n):
    mmm = 1
    for i in range(1,n+1):
        mmm *= i
    return mmm

N = int(input())
city = []
for i 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):
        dist = ((city[i][0]-city[j][0])**2 + (city[i][1]-city[j][1])**2)**0.5
        ans += dist*(2*fact(N-1))

print(ans / fact(N))

Solution (Python):
import math
N=int(input())
x=[0]*N
y=[0]*N
for i in range(0,N):
    x[i],y[i]=map(int,input().split())
sum=0
count=0
for i in range(0,N):
    for j in range(0,N):
        sum+=math.sqrt((x[i]-x[j])**2+(y[i]-y[j])**2)
        count+=1
print(sum*N/count)

Solution (Python):
from fractions import gcd
from math import sqrt
from collections import deque,defaultdict,Counter
from heapq import heapify,heappop,heappush
from copy import deepcopy
from itertools import accumulate,permutations
from bisect import bisect_left,bisect_right

N = int(input())
xy = [[int(i) for i in input().split()] for _ in range(N)]

states = list(permutations(list(range(N))))

ans = 0
for state in states:
    x,y = xy[state[0]]
    dist = 0
    for i in state[1:]:
        nx,ny = xy[i]
        dist += sqrt(pow(nx - x, 2) + pow(ny - y, 2))
        x,y = nx,ny
    ans += dist

print(ans / len(states))

Solution (Python):
import sys
from math import sqrt
from itertools import permutations as permi
input = sys.stdin.readline
N = int(input())
ps = []
for _ in range(N): 
  u, v = map(int, input().split())
  ps.append((u, v))
res = 0
c = 0
for p in permi([x for x in range(N)], N):
  t = 0
  c += 1
  for i in range(N - 1):
    x = p[i]
    y = p[i + 1]
    t += sqrt((ps[x][0] - ps[y][0]) ** 2 + (ps[y][1] - ps[x][1]) ** 2)
  
  res += t
print(res / c)

Solution (Python):
import sys
from itertools import permutations
def main():
    input = sys.stdin.readline
    N = int(input())
    xy = [tuple(map(int, input().split())) for _ in range(N)]
    def dist(x1,y1,x2,y2): return ((x1-x2)**2 + (y1-y2)**2)**0.5
    ans = 0
    for route in permutations(range(N)):
        for i in range(N-1):
            ans += dist(xy[route[i]][0],xy[route[i]][1],xy[route[i+1]][0],xy[route[i+1]][1])
    for i in range(1,N+1):
        ans /= i
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from itertools import permutations

def fact(n):
    if n == 0:
        return 1
    return n * fact(n-1)

N = int(input())
xy = [tuple(map(int, input().split())) for _ in range(N)]
s = 0
for p in permutations(list(range(N))):
    for i in range(N-1):
        dx = xy[p[i+1]][0] - xy[p[i]][0]
        dy = xy[p[i+1]][1] - xy[p[i]][1]
        s += (dx**2+dy**2)**.5
print(s/fact(N))

Solution (Python):
def main():
    N = int(input())
    ans = 0
    from itertools import permutations
    from math import hypot
    XY = [[int(i) for i in input().split()] for j in range(N)]
    for p in permutations(range(N)):
        cur = 0
        for i in range(N-1):
            cur += hypot(XY[p[i]][0] - XY[p[i+1]][0],
                         XY[p[i]][1] - XY[p[i+1]][1])
        ans += cur
    fact = 1
    for i in range(1, N+1):
        fact *= i
    print(ans / fact)


if __name__ == '__main__':
    main()

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
n = INT()
xy = [LIST() for _ in range(n)]
a = list(permutations(xy, n))
l = len(a)
ans = 0
for i in range(l):
    tmp = 0
    for j in range(n - 1):
        tmp += sqrt((a[i][j][0] - a[i][j+1][0]) ** 2 + (a[i][j][1] - a[i][j+1][1]) ** 2)
    ans += tmp
ans /= l
print(ans)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
from math import sqrt
a=[]
for _ in range(int(input())):
    a.append([int(i) for i in input().split()])
summ=0
for i in a:
    for j in a:
        summ+=sqrt((i[0]-j[0])**2+(i[1]-j[1])**2)
print(summ/len(a))

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
from itertools import combinations_with_replacement as cwr , combinations , permutations ,product
from math import sqrt
a=[]
for _ in range(int(input())):
    a.append([int(i) for i in input().split()])
p=list(permutations(a))
ans=[]
for i in p:
    cur=0
    for j in range(len(i)-1):
        cur+=sqrt((i[j+1][0]-i[j][0])**2+(i[j+1][1]-i[j][1])**2)
    ans.append(cur)
print(sum(ans)/len(ans))

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
from itertools import combinations_with_replacement as cwr , combinations , permutations ,product
from math import sqrt
a=[]
for _ in range(int(input())):
    a.append([int(i) for i in input().split()])
p=list(permutations(a))
ans=[]
for i in p:
    cur=0
    for j in range(len(i)-1):
        cur+=sqrt((i[j+1][0]-i[j][0])**2+(i[j+1][1]-i[j][1])**2)
    ans.append(cur)
print(sum(ans)/len(ans))

Solution (Python):
import itertools
import math
N=int(input())
town=[list(map(int,input().split())) for _ in range(N) ]
sum=0
cnt=0
for path in itertools.permutations(town,N):
    cnt+=1
    for i in range(N-1):
        sum+=math.sqrt((path[i][0]-path[i+1][0])**2+(path[i][1]-path[i+1][1])**2)
print(sum/cnt)

Solution (Python):
import itertools
import math

N = int(input())
xy  = [[int(i) for i in input().split()] for j in range(N)]
distance = [[0 for j in range(N)] for i in range(N)]
for i in range(N):
    for j in range(N):
        xi = xy[i][0]
        yi = xy[i][1]
        xj = xy[j][0]
        yj = xy[j][1]
        d = math.sqrt((xi-xj)**2+(yi-yj)**2)
        distance[i][j] = d
        distance[j][i] = d

print(sum([sum(i) for i in distance])/N)

Solution (Python):
import itertools
import math

N = int(input())
xy  = [[int(i) for i in input().split()] for j in range(N)]
distance = [[0 for j in range(N)] for i in range(N)]
for i in range(N):
    for j in range(N):
        xi = xy[i][0]
        yi = xy[i][1]
        xj = xy[j][0]
        yj = xy[j][1]
        d = math.sqrt((xi-xj)**2+(yi-yj)**2)
        distance[i][j] = d
        distance[j][i] = d

anslist=[]
for route in itertools.permutations(range(N),N):
    total=0
    for i in range(N-1):
        start = route[i]
        goal = route[j]
        total += distance[start][goal]
    anslist.append(total)

print(sum(anslist)/len(anslist))

Solution (Python):

from itertools import permutations
from math import factorial
n=int(input())
xy=[tuple(map(int,input().split())) for _ in range(n)]

res=0
for l in permutations(range(n)):
    res+=sum([((xy[l[i+1]][0]-xy[l[i]][0])**2+(xy[l[i+1]][1]-xy[l[i]][1])**2)**0.5 for i in range(n-1)])
print(res/factorial(n))

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

Solution (Python):
import math
n = int(input())
coo = [list(map(int,input().split())) for i in range(n)]
sum = 0
for i in range(n):
    for j in range(i,n):
        sum += math.sqrt((coo[i][0]-coo[j][0])**2 + (coo[i][1]-coo[j][1])**2)

ans = 2 * sum / float(n)
print(ans)

Solution (Python):
import itertools
import math
N = int(input())
xy = [list(map(int,input().split())) for i in range(N)]
s = list(range(N))
sum = 0
for v in itertools.permutations(s):
    for i in range(N-1):
        distance = math.sqrt((xy[v[i]][0]-xy[v[i+1]][0])**2 + (xy[v[i]][1]-xy[v[i+1]][1])**2)
        sum += distance
print(sum/math.factorial(N))

Solution (Python):
import itertools
import math

def solve(l):
    r = 0
    for i in range(len(l)-1):
        x_i = l[i][0]
        y_i = l[i][1]
        x_i_1 = l[i+1][0]
        y_i_1 = l[i+1][1]

        r += math.sqrt(pow(x_i_1 - x_i,2) + pow(y_i_1 - y_i,2))

    return r

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

    p = list(itertools.permutations(xy, len(xy)))
    result = 0

    for i in range(len(p)):
        result += solve(list(p[i]))

    print(result/len(p))



if __name__ == "__main__":
    main()

Solution (Python):
import itertools
import math


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

pairs = list(itertools.permutations(A, N))

ans = 0
for p in pairs:
    x1, y1 = p[0]
    for i in range(1, N):
        x2, y2 = p[i]
        ans += math.hypot(x1-x2, y1-y2)
        x1, y1 = x2, y2

ans /= len(pairs)
print(ans)

Solution (Python):
import itertools
import math


def calc_diff(a, b):
    x = (a[0] - b[0])
    y = (a[1] - b[1])
    return math.sqrt(x**2 + y**2)


N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
pairs = list(itertools.product(A, A))
pairs = [calc_diff(p[0], p[1]) for p in pairs]
ans = sum(pairs) / 2 * 2 / N
print(ans)

Solution (Python):
n = int(input())
s = [list(map(int,input().split())) for i in range(n)]
from itertools import permutations
perm = list(permutations(s,n))
def distance(s):
    res = 0
    for i in range(n-1):
        res += ((s[i][0]-s[i+1][0])**2 + (s[i][1]-s[i+1][1])**2)**0.5
    return res
k = 0
for key in perm:
    k += distance(key)
fin_res = format(k/len(perm),'.10f')
print(fin_res)

Solution (Python):
n = int(input())
s = [list(map(int,input().split())) for i in range(n)]
from itertools import permutations
def distance(s):
    res = 0
    for i in range(n-1):
        res += ((s[i][0]-s[i+1][0])**2 + (s[i][1]-s[i+1][1])**2)**0.5
    return res
k = 0
for key in list(permutations(s,n)):
    k += distance(key)
fin_res = format(k/len(list(permutations(s,n))),'.10f')
print(fin_res)

Solution (Python):


def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF = float("inf")
import itertools

N = INT()
xy = [tuple(MAP()) for _ in range(N)]

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

print(sum(dist_list)/len(dist_list))

Solution (Python):
from itertools import permutations

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

Length = []
permutation = list(permutations(range(0, N)))

for i in range(len(permutation)):
    L = 0
    for j in range(len(permutation[i]) - 1):
        L += (
            (place[permutation[i][j]][0] - place[permutation[i][j + 1]][0]) ** 2
            + (place[permutation[i][j]][1] - place[permutation[i][j + 1]][1]) ** 2
        ) ** (1 / 2)
    Length.append(L)

print(sum(Length) / len(permutation))

Solution (Python):
import math
import itertools
def distance(x1,x2,y1,y2):
    return math.sqrt(((x2-x1)**2) + ((y2-y1)**2))
n = int(input())
x = [0 for _ in range(n)]
y = [0 for _ in range(n)]
t = [i for i in range(n)]
for i in range(len(x)):
    x[i],y[i] = map(int,input().split())
pattern = [_ for _ in itertools.permutations(t,n)]
dis_all = [0 for _ in range(len(pattern))]
for i in range(len(pattern)):
    for j in range(n-1):
        dis_all[i] += distance(x[pattern[i][j]],x[pattern[i][j+1]],y[pattern[i][j]],y[pattern[i][j+1]])
print(sum(dis_all)/len(dis_all))

Solution (Python):
import itertools
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
permu_list = itertools.permutations(range(N))
ans=0
c = 0
for p in permu_list:
  c += 1
  for i in range(N-1):
    ans += ((A[p[i]][0]-A[p[i+1]][0])**2+(A[p[i]][1]-A[p[i+1]][1])**2)**0.5
print(ans/c)

Solution (Python):
n=int(input())
XY=[]
for i in range(n):
  XY.append(tuple(map(int,input().split())))
def d(x1,y1,x2,y2):
  return ((x2-x1)**2+(y2-y1)**2)**0.5
ans=0
for i in range(n):
  for j in range(i+1,n):
    ans+=d(XY[i][0],XY[i][1],XY[j][0],XY[j][1])*2/n
print(ans)

Solution (Python):
N = int(input())
XY = [tuple(map(int, input().split())) for _ in range(N)]

def dist(x, y, u, v):
    return ((x - u)**2 + (y - v)**2)**0.5

ans = 0
for i, (x, y) in enumerate(XY):
    for u, v in XY[i + 1:]:
        ans += dist(x, y, u, v)

print(2 * ans / N)

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

N = int(input())
points = [tuple([int(x) for x in input().split()]) for _ in range(N)]

routes = permutations(range(N), r=N)

sum_dist = 0
for r in routes:
    for i in range(N - 1):
        (x_0, y_0), (x_1, y_1) = points[r[i]], points[r[i + 1]]
        sum_dist += ((x_0 - x_1)**2 + (y_0 - y_1)**2)**0.5

print(sum_dist / factorial(N))

Solution (Python):
from itertools import permutations
from math import sqrt, factorial
import sys
input = sys.stdin.readline


def dist(xy1, xy2):
    x1, y1 = xy1
    x2, y2 = xy2
    return sqrt((x1-x2)**2 + (y1-y2)**2)


def main():
    n = int(input())
    lst = [tuple(map(int, input().split())) for _ in range(n)]
    sum_d = 0
    for perm in permutations(range(n)):
        d = 0
        for i in range(n-1):
            d += dist(lst[perm[i]], lst[perm[i+1]])
        sum_d += d
    print(sum_d / factorial(n))


if __name__ == "__main__":
    main()

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

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

avg = 0.0
count = 0
for perm in permutations(range(N)):
    count += 1
    
    cost =  0
    for i in range(N - 1):
        pi, pj = perm[i], perm[i + 1]
        dij = ((xy[pi][0] - xy[pj][0]) ** 2 + (xy[pi][1] - xy[pj][1]) ** 2) ** 0.5
        cost += dij
    avg += cost
print(avg / count)

Solution (Python):
import math
import copy
from copy import deepcopy
import sys
import fractions

from functools import reduce

import heapq
import collections
import itertools
sys.setrecursionlimit(100001)






def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList




n = int(input())


inputDataList = []
data = []
for i in range(n):
    inputData = input().split()
    inputDataList = [int(n) for n in inputData]
    data.append(inputDataList)

mat = [[-1 for i in range(n)] for j in range(n)] 


def calc_dis(x1, y1, x2, y2):
    dis = pow(x1 - x2, 2) + pow(y1 - y2, 2)
    dis = math.sqrt(dis)
    return dis


def path_dis(path):
    dis = 0
    for i in range(len(path)-1):
        dis += mat[path[i]][path[i+1]]
    return dis

for i in range(n):
    for j in range(n):
        mat[i][j] = calc_dis(data[i][0], data[i][1], data[j][0], data[j][1])

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

ans = 0
for p in perm:
    tmp_ans = path_dis(p)
    ans += tmp_ans

ans = ans/len(perm)
print(ans)

Solution (Python):
N = int(input())
Plist = []
c = 0
for i in range(N):
    c += i
    Plist.append(list(map(int,input().split())))
import math
    
D = 0
for j in range(N):
    for k in range(N):
        if j <= k :
            continue
        D += math.sqrt((Plist[j][0]-Plist[k][0])**2 + (Plist[j][1]-Plist[k][1])**2)
print(D*(N-1)/c)

Solution (Python):
import math
from collections import defaultdict
import itertools
N=int(input())
d=defaultdict(float)
l=[]
for i in range(N):
  x,y=map(int,input().split())
  l.append([x,y])
for i in range(N-1):
  for j in range(i+1,N):
    x1,y1=l[i][0],l[i][1]
    x2,y2=l[j][0],l[j][1]
    d[(i,j)]=(math.sqrt((x1-x2)**2+(y1-y2)**2))
    d[(j,i)]=(math.sqrt((x1-x2)**2+(y1-y2)**2))

tot=0
for pat in itertools.permutations([i for i in range(N)]):
  for i in range(N-1):
    tot+=(d[(pat[i],pat[i+1])])
print(tot/math.factorial(N))

Solution (Python):
import math
N=int(input())
d=[]
l=[]
for i in range(N):
  x,y=map(int,input().split())
  l.append([x,y])
for i in range(N-1):
  for j in range(i+1,N):
    x1,y1=l[i][0],l[i][1]
    x2,y2=l[j][0],l[j][1]
    d.append(math.sqrt((x1-x2)**2+(y1-y2)**2))
print(2*sum(d)/N)

Solution (Python):
from math import sqrt
from itertools import permutations
def dist(a,b):
    return sqrt((a[0]-b[0])**2+(a[1]-b[1])**2)
n = int(input())
data = [list(map(int,input().split())) for _ in range(n)]

ans = 0
for q in permutations(data):
    for i in range(1,n):
        ans += dist(q[i-1],q[i])
for i in range(n):
    ans /= (i+1)
print(ans)

Solution (Python):
from math import sqrt
def dist(a,b):
    return sqrt((a[0]-b[0])**2+(a[1]-b[1])**2)
n = int(input())
data = [list(map(int,input().split())) for _ in range(n)]

ans = 0
for i in range(n):
    for j in range(n):
        ans += dist(data[i],data[j])

print(ans/n)

Solution (Python):
from math import sqrt
def dist(a,b):
    return sqrt((a[0]-b[0])**2+(a[1]-b[1])**2)
n = int(input())
data = [list(map(int,input().split())) for _ in range(n)]

ans = 0
for i in range(n):
    for j in range(n):
        ans += dist(data[i],data[j])

print(ans/n)

Solution (Python):
from math import sqrt
from itertools import permutations
def dist(a,b):
    return sqrt((a[0]-b[0])**2+(a[1]-b[1])**2)
n = int(input())
data = [list(map(int,input().split())) for _ in range(n)]

ans = 0
for q in permutations(data):
    for i in range(1,n):
        ans += dist(q[i-1],q[i])
for i in range(n):
    ans /= (i+1)
print(ans)

Solution (Python):
import itertools
import math

n = int(input())
l = []
x = []
y = []
for i in range(n):
    l.append(i+1)
    tmp_x, tmp_y = map(int, input().split())
    x.append(tmp_x)
    y.append(tmp_y)

permutation = list(itertools.permutations(l, n))

ans = 0
for per in itertools.permutations(l, n):
    for i in range(0, n-1):
        suffix = per[i]
        ans += math.sqrt((x[per[i]-1] - x[per[i+1]-1])**2 + (y[per[i]-1] - y[per[i+1]-1])**2)

print(ans / len(permutation))

Solution (Python):
n=int(input())
l=[list(map(int,input().split())) for _ in range(n)]
print(sum(((x-z)**2+(y-w)**2)**.5 for x,y in l for z,w in l)/n)

Solution (Python):
n = int(input())
ll = [list(map(int,input().split())) for _ in range(n)]
import itertools as it
c,d = 0,0
for t in it.permutations(range(n)):
  c += 1
  for i in range(len(t)-1):
    d += ((ll[t[i+1]][1]-ll[t[i]][1])**2+(ll[t[i+1]][0]-ll[t[i]][0])**2)**.5
print(d/c)

Solution (Python):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


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


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False



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


def main():
    N = I()
    x = [0] * N
    y = [0] * N

    for i in range(N):
        x[i], y[i] = MI()

    ans = 0
    for cities in permutations(range(N)):
        for i in range(1, len(cities)):
            ans += distance(x[cities[i-1]], y[cities[i-1]], x[cities[i]], y[cities[i]])

    print(ans / math.factorial(N))


if __name__ == '__main__':
    main()

Solution (Python):
import itertools
import math

N = int(input())
town = list(itertools.permutations(range(N)))
dis = []
for i in range(N):
    s = tuple(map(int,input().split()))
    dis.append(s)
    
ans = 0
for i in town:
    for j in range(len(i)-1):
        calc =  math.sqrt((dis[i[j]][0]-dis[i[j+1]][0])**2 + (dis[i[j]][1]-dis[i[j+1]][1])**2) 
        ans += calc
    
print(ans/len(town))