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 sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

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

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

L2 = []
for i in range(N):
    for j in range(N):
        if i != j:
            L2.append(length(L[i][0], L[i][1], L[j][0], L[j][1]))

print(sum(L2)/N)

Solution (Python):
import math

def dist(XY, i, j):
  return math.sqrt((XY[i][0] - XY[j][0]) ** 2 + (XY[i][1] - XY[j][1]) ** 2)

N = int(input())
XY = [[0, 0] for _ in range(N)]
for i in range(N):
  XY[i] = [int(x) for x in input().split()]
D = [[0.0 for _ in range(N)] for _ in range(N)]
E = 0.0
for i in range(N):
  for j in range(N):
    E += dist(XY, i, j) / float(N)
print(E)

Solution (Python):


import math

def getSumOfD(N, XY, flags, n, d, x, y):
    if n == N:
        return d

    sumOfD = 0

    for i in range(N):
        if not flags[i]:
            flags[i] = True
            x2, y2 = XY[i]

            sumOfD += getSumOfD(
                N, XY, flags, n+1,
                d + math.sqrt((x2-x)**2 + (y2-y)**2),
                x2, y2)
            
            flags[i] = False
        
    return sumOfD


def getFact(n):
    x = 1
    for i in range(2, n+1):
        x *= i

    return x


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

    sumOfD = 0
    flags = [False]*N

    for i in range(N):
        flags[i] = True
        x, y = XY[i]
        sumOfD += getSumOfD(N, XY, flags, 1, 0, x, y)
        flags[i] = False

    print('{:.9f}'.format(sumOfD/getFact(N)));



if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
P = []

for i in range(N):
    x, y = map(int, input().split())
    P.append((x, y))
d = 0
k = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        k += 1
        d += ((P[i][0] - P[j][0]) ** 2 + (P[i][1] - P[j][1]) ** 2) ** 0.5

print(d / k * (N - 1))

Solution (Python):
n= int(input())
s=0
a=[]


def solve(p):
	x,y = p[0][0], p[0][1]
	t=0
	for i in range(1,n):
		
		t+= (( x- p[i][0])**2 + (y- p[i][1])**2)**0.5
		x= p[i][0]
		y= p[i][1]

	return t

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


z = list(itertools.permutations(a))

for i in z:
	
	s+=solve(i)









for i in range(1,n+1):
	s/= i
print(s)

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 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()))
import itertools
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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


N = INT()
b = []
for i in range(N):
  a = LIST()
  b.append(a)


jun = [i for i in range(N)]
c = list(itertools.permutations(jun))


ans2 = 0
for j in c:
  
  ans = 0
  
  for i in range(len(j)-1):
    
    
    x1 = b[j[i]][0]
    x2 = b[j[i+1]][0]
    y1 = b[j[i]][1]
    y2 = b[j[i+1]][1]
    ans += dist(x1, x2, y1, y2)
    
  
  ans2 += ans
  
    
print(ans2/len(c))

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())

Kai = math.factorial(N)
C = N * (N-1) // 2
pathcount = Kai * (N-1) // C
Ans = 0
dist = 0

for j in range(N):
  for k in range(N):
    if j < k:
      dist = dist + ((x[j] - x[k]) ** 2 + (y[j] - y[k]) ** 2)** 0.5

Ans = dist * pathcount / Kai
print(Ans)

Solution (Python):
import math
n = int(input())
total = 0
towns = []
for _ in range(n):
    x, y = map(int, input().split())
    for t in towns:
        total += math.sqrt( (t[0]-x)**2 + (t[1]-y)**2 )
    towns.append([x,y])

print(total*2/n)

Solution (Python):
import itertools
import math
def distance(a,b,c,d):
    return ((a-c)**2 + (b-d)**2)**0.5
n = int(input())
x = [list(map(int,input().split())) for i in range(n)]
seq = [i for i in range(n)]
dis = 0
for s in list(itertools.permutations(seq)):
    for i in range(n-1):
        dis = dis + distance(x[s[i]][0],x[s[i]][1],x[s[i+1]][0],x[s[i+1]][1])
print(dis/math.factorial(n))

Solution (Python):


def kyori(a,b):
	
	return ((a[0]-b[0])**2+(a[1]-b[1])**2)**0.5
def bikkuri(n):
	if(n==1):
		return 1
	else:
		return n*bikkuri(n-1)
N=int(input())
zahyo=[[0,0]]*8
for i in range(N):
	zahyo[i]=list(map(int,input().split()))
goukei=0
for i in range(N):
	for j in range(N):
		goukei+=kyori(zahyo[i],zahyo[j])
print(goukei/N)

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

import itertools
import math

ans = 0
for l in list(itertools.permutations(range(n))):
    tmp = 0
    for i in range(len(l) - 1):
        tmp += math.sqrt((xy[l[i]][0] - xy[l[i+1]][0]) ** 2 + (xy[l[i]][1] - xy[l[i+1]][1]) ** 2)
    ans += tmp
print(ans / len(list(itertools.permutations(range(n)))))

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

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

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

Solution (Python):

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

res=0
def func(n):
	x=1
	for i in range(1,n+1):
		x*=i
	return x

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

Solution (Python):
import sys,itertools
def input():
    return sys.stdin.readline()[:-1]

N = int(input())
dp = {}
for i in range(N):
    dp[i] = list(map(int, input().split()))

MAP = [None]*N
for i in range(N):
    MAP[i] = [0]*N

for i in range(N):
    x_1,y_1 = dp[i]
    for j in range(N):
        x_2,y_2 = dp[j]
        if i==j:
            continue
        else:
            MAP[i][j] =((x_1-x_2)**2+(y_1-y_2)**2)**.5

cnt = 0
k = 0
for i in itertools.permutations(range(N)):
    tmp = 0
    c = 0
    for j in i:
        if c:
            tmp += MAP[pre][j]
        pre = j
        c += 1
    cnt += tmp
    k += 1
print(cnt/k)

Solution (Python):
import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
sys.setrecursionlimit(10 ** 7)

from math import factorial
from itertools import permutations

def main():
  n = ni()
  xy = [na() for _ in range(n)]

  ff = lambda a, b, c, d: ((a - b) ** 2 + (c - d) ** 2) ** 0.5

  res = []
  for per in permutations(range(n)):
    tmp = 0
    for i, pp in enumerate(per[:-1]):
      tmp += ff(xy[pp][0], xy[per[i+1]][0], xy[pp][1], xy[per[i+1]][1])
    res.append(tmp)
  print(sum(res) / factorial(n))


if __name__ == '__main__':
  main()

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

Solution (Python):
import math
import itertools
N = int(input())
X = []
Y = []

for _ in range(N):
	x, y = map(int, input().split())
	X.append(x)
	Y.append(y)
ret = 0	

for lst in itertools.permutations(range(N)):
	for i in range(1, N):
		ret += math.sqrt((X[lst[i]] - X[lst[i - 1]]) ** 2 + (Y[lst[i]] - Y[lst[i - 1]]) ** 2)
		
print(ret / math.factorial(N))

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


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

    def distance(c1, c2):
        square_x = (c1[0] - c2[0]) ** 2
        square_y = (c1[1] - c2[1]) ** 2
        return (square_x + square_y) ** (1/2)

    total = [0] * N
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            total[i] += distance(coordinates[i], coordinates[j])

    print(sum(total)/N)


if __name__ == '__main__':
    answer()

Solution (Python):
import itertools
import math

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

point_index = list(range(N))

p = list(itertools.permutations(point_index))

total = 0
for lst in p:
    for i in range(N-1):
        distance = math.sqrt((point_list[lst[i]][0] - point_list[lst[i+1]][0])**2 + (point_list[lst[i]][1] - point_list[lst[i+1]][1])**2)
        total += distance

print(total / math.factorial(N))

Solution (Python):
N=int(input())
X=[]
Y=[]
for _ in range(N):
    x,y=map(int,input().split())
    X.append(x)
    Y.append(y)
from itertools import *
c=list(permutations(list(range(N)),N))
ans=0
for i in c:
    for j in range(N-1):
        ans+=((X[i[j]]-X[i[j+1]])**2+(Y[i[j]]-Y[i[j+1]])**2)**0.5
print(ans/len(c))

Solution (Python):
import itertools
import math
N = int(input())
xy = []
for i in range(N):
    a, b = map(int, input().split())
    xy.append([a,b])

s = 0

waru = math.factorial(N)
for v in itertools.permutations(xy, N):
    for i in range(len(v)-1):
        s += math.sqrt(pow(v[i][0]-v[i+1][0],2) + pow(v[i][1]-v[i+1][1],2))
print(float(s)/waru)

Solution (Python):


n=int(input())

xy=[]

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

d=0

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

print(d*2/n)

Solution (Python):
import itertools
n=int(input())
towns=[list(map(int,input().split())) for i in range(n)]
ite=[i for i in range(n)]
ans=0
for i in itertools.permutations(ite):
  for j in range(n-1):
    ans+=(((towns[i[j+1]][1]-towns[i[j]][1])**2+(towns[i[j+1]][0]-towns[i[j]][0])**2)**0.5)
div=1
for i in range(1,n+1):
  div*=i
print(ans/div)

Solution (Python):
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 i in range(n):
    for j in range(i+1,n):
        ans += 2/n * ( (x[i]-x[j])**2 + (y[i]-y[j])**2)**0.5
print(ans)

Solution (Python):



import math


def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True


def main():

    n = int(input())
    xy=[]
    for i in range(n):
        xy.append(list(map(int,input().split())))
    d = []
    for i in range(0,n-1):
        for j in range(i+1,n):
            d.append(math.sqrt((xy[i][0]-xy[j][0])**2+(xy[i][1]-xy[j][1])**2))

    ave=n*(n-1)//2
    aveve=math.factorial(n)*(n-1)
    aveve2=aveve//ave
    ave2=sum(d)*aveve2/(math.factorial(n))
    print(ave2)

if __name__ == "__main__":
    main()

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

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

N = int(input())
c = 1
for n in range(1, N + 1):
    c *= n
ans = [0] * c
xy = [0] * N
for n in range(N):
    xy[n] = tuple([int(x) for x in input().strip().split()])

i = 0
for xy_ in permutations(xy, N):
    pos = -1
    pre = 0
    ans_ = 0
    for n in range(N):
        if pos == -1:
            pre = xy_[n]
        pos = xy_[n]
        ans_ += dist(pre[0], pre[1], pos[0], pos[1])
        pre = pos
    ans[i] += ans_
    i += 1

print(sum(ans) / c)

Solution (Python):

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


import numpy as np
from itertools import permutations
from math import factorial
N = read_a_int()
zahyou = []
for _ in range(N):
    zahyou.append(read_ints())

zahyou = np.array(zahyou)
toori = factorial(N)



def get_length(zahyou, keiro: list):
    zahyou1 = zahyou[keiro[:-1], :]
    zahyou2 = zahyou[keiro[1:], :]
    ret = np.linalg.norm(zahyou1 - zahyou2, axis=1).sum()
    return ret


ans = 0
for keiro in permutations(list(range(N))):
    ans += get_length(zahyou, keiro) / toori

print(ans)

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

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

cnt = 0
for i, j in combinations(range(N), 2):
    cnt += ((X[i][0] - X[j][0]) ** 2 + (X[i][1] - X[j][1]) ** 2) ** 0.5

print(factorial(N - 1) * 2 * cnt / factorial(N))

Solution (Python):
from itertools import permutations
from math import factorial
N = int(input())
city = [list(map(int,input().split())) for i in range(N)]
result = 0
for v in permutations(city):
  for c in range(1, N):
    result += ((v[c-1][0] - v[c][0]) ** 2 + (v[c-1][1] - v[c][1]) ** 2) ** 0.5
print(result / factorial(N))

Solution (Python):
from math import hypot
from math import factorial

n = int(input())
a = [tuple(map(int, input().split())) for _ in range(n)]
m = factorial(n - 1)
ret = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        ret += hypot(a[i][0] - a[j][0], a[i][1] - a[j][1]) * m
print(ret / factorial(n))

Solution (Python):


import math
import os
import sys


def main():
    N = read_int()
    A = [tuple(read_ints()) for _ in range(N)]
    print(solve(N, A))


def fact(x):
    f = 1
    while x > 1:
        f *= x
        x -= 1
    return f


def solve(N, A):
    s = 0.0
    f = fact(N)
    e = f * (N - 1) // (N * (N - 1) // 2)
    for i in range(N):
        for j in range(i + 1, N):
            s += math.sqrt((A[j][0] - A[i][0]) ** 2 + (A[j][1] - A[i][1]) ** 2)
    dprint(s, e, f)
    return (e * s) / f




DEBUG = 'DEBUG' in os.environ


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


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()

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


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

cnt = 0
dist = 0.0
for vx in itertools.permutations(vL):
    d = 0.0
    cnt += 1
    for x,y in zip(vx[:-1],vx[1:]):
        tA, tB = vC[x], vC[y]
        d += ((tA[0]-tB[0])**2 + (tA[1]-tB[1])**2)**.5
    dist += d

print(dist/cnt)

Solution (Python):
import itertools

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

all = list(itertools.permutations(x))
q=0
for i in range(len(all)):
    for j in range(n-1):
       q+= ((all[i][j][0]-all[i][j+1][0])**2+(all[i][j][1]-all[i][j+1][1])**2)**0.5

print(q/len(all))

Solution (Python):
import math
N = int(input())
XY = [[int(x) for x in input().split()] for _ in range(N)]
s = 0
for i in range(N):
    for j in range(i+1, N):
        xi, yi = XY[i]
        xj, yj = XY[j]
        s += (math.sqrt((xi-xj)**2 + (yi-yj)**2))
print(2*s/N)

Solution (Python):
from itertools import permutations
import math

N=int(input())
T=[] 
lenlist=[] 

for _ in range(N): 
    t=list(map(int,input().split(" ")))
    T.append(t)


for p in list(permutations(T,N)):
    lsum=0

    
    for pxi in range(1,len(p)):
        l=math.sqrt((p[pxi][0]-p[pxi-1][0])**2+(p[pxi][1]-p[pxi-1][1])**2)
        lsum+=l

    lenlist.append(lsum)

print(sum(lenlist)/len(lenlist))

Solution (Python):
words = lambda t : list(map(t, input().split()))
n = int(input())
xys = []
for i in range(n):
    x,y = words(int)
    xys.append((x,y))

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

fn = math.factorial(n)
nc2 = math.factorial(n) // (math.factorial(2) * math.factorial(n-2))

ans = 0
for i in range(n-1):
    for j in range(i,n):
        d = distance(xys[i][0], xys[i][1], xys[j][0], xys[j][1])
        ans += d * (fn // nc2)

print(ans*(n-1)/fn)

Solution (Python):
import itertools
N = int(input())
X = [0] * N
Y = [0] * N
acc = 0
c = len(list(itertools.combinations(range(N), 2)))
for i in range(N):
    x, y = map(int, input().split())
    X[i] = x
    Y[i] = y
for p in itertools.permutations(range(N), 2):
    a = p[0]
    b = p[1]
    acc += ((X[a] - X[b]) ** 2 + (Y[a] - Y[b]) ** 2) ** (1/2)
print(acc/c*(N-1)/2)

Solution (Python):
import itertools
import math

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

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

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

seq = []
for i in range(N):
    seq.append(i)

sum1 = 0.0
for a in itertools.permutations(seq):
    for i in range(N-1):
        sum1 += distance(Data[a[i]], Data[a[i+1]])
print( sum1 / float(fact(N)))

Solution (Python):
import math
n = int(input())
p = []
dis = []
for i in range(n):
  x,y = map(int, input().split())
  p.append([x,y])
for i in range(n):
  for j in range(n):
    if i != j:
      dx = p[i][0] - p[j][0]
      dy = p[i][1] - p[j][1]
      dis.append(math.sqrt(dx*dx + dy*dy)/n)
print(round(sum(dis), 10))

Solution (Python):
import sys
from itertools import combinations, permutations

input = sys.stdin.readline

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

ans = 0
npath = N*(N-1)
for i,j in permutations(range(N),2):
	dist = ( (xy[i][0]-xy[j][0])**2 + (xy[i][1]-xy[j][1])**2 )**0.5
	ans += dist/npath*(N-1)

print(ans)

Solution (Python):
import itertools
import math

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

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

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

total = 0.0

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

for p in permutations:
    for i in range(len(p) - 1):
        x1, y1 = path[p[i]]
        x2, y2 = path[p[i + 1]]
        d = distance(x1,y1,x2,y2)
        total += d

print(total / len(permutations))

Solution (Python):
import itertools

n=int(input())
div = 1
for i in range(1,n+1):
    	div*=i
xy = [[int(i) for i in input().split()] for i in range(n)]

_sum = 0

for _list in itertools.permutations([i for i in range(n)]):
	distance = 0
	for i in range(n-1):
    		distance += ((xy[_list[i]][0] - xy[_list[i+1]][0])**2 + (xy[_list[i]][1] - xy[_list[i+1]][1])**2)**0.5
	_sum += distance
print(_sum/div)

Solution (Python):
import itertools
import math

def main():
    n = int(input())
    A = [list(map(int, input().split())) for i in range(n)]
    total = 0
    L = list(itertools.permutations(range(n), n))
    for l in L:
        l1, *la = l
        for i in la:
            total += ((A[l1][0]-A[i][0])**2 + (A[l1][1]-A[i][1])**2)**0.5
            l1 = i
    print(total/math.factorial(n))


if __name__ == '__main__':
    main()

Solution (Python):
import itertools
import math

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

_sum = 0
for v in itertools.permutations(XY, N):
    for i in range(1, len(v)):
        ve = (v[i][0]-v[i-1][0])**2 +  (v[i][1]-v[i-1][1]) ** 2
        _sum += math.sqrt(ve)

print(_sum/math.factorial(N))

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

if __name__=="__main__":
    sol()

Solution (Python):
import math


def permutation(n, elems):
    if n == 0:
        return []
    elif n == 1:
        return [elems]
    else:
        result = []
        for q in elems:
            new_p = list(elems)
            new_p.remove(q)
            ac = permutation(n - 1, new_p)
            result += [[q] + a for a in ac]
        return result


def calc(N, xlist):
    d = {}
    for i in range(N):
        x = xlist[i]
        d[i] = {}
        for j in range(N):
            y = xlist[j]
            d[i][j] = math.sqrt((x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2)
    perms = permutation(N, list(range(N)))
    result = 0
    for p in perms:
        for i in range(N - 1):
            result += d[p[i]][p[i + 1]]
    result /= len(perms)
    return result


N = int(input())
x = [tuple(int(s) for s in input().split()) for _ in range(N)]
print(calc(N, x))

Solution (Python):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline






















def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N = inputInt()
	xy = []
	seq = []

	for i in range(N):
		x,y = inputMap()
		xy.append((x,y))
		seq.append(i)

	ptns = list(itertools.permutations(seq))

	anss = []
	for ptn in ptns:
		ptn_list = list(ptn)

		strt = 0
		for i,val in enumerate(ptn_list):
			if i == 0:
				strt = val
				continue

			stx, sty = xy[strt]
			sdx, sdy = xy[val]
			tmptmp = ((stx-sdx)**2) + ((sty-sdy)**2)
			tmp = math.sqrt(tmptmp)
			anss.append(tmp)

	ans = 0
	for i in anss:
		ans += i

	print(ans/len(ptns))




if __name__ == "__main__":
	main()

Solution (Python):

import itertools
import math

N = int(input().split()[0])
xy_list = []

for _ in range(N):
    x, y = list(map(int, input().split()))
    xy_list.append((x, y))

l = list(range(N))
p_list = list(itertools.permutations(l))
m_list = []
total = 0
count = 0
for p in p_list:
    count += 1
    t = 0
    for i, a in enumerate(p[:-1]):
        ax, ay = xy_list[a]
        bx, by = xy_list[p[i + 1]]
        t += ((ax - bx) ** 2 + (ay - by) ** 2) ** 0.5
    total += t

ans = total / count

print(ans)

Solution (Python):
import itertools

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

for i in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
    R.append(i)

L = 0
cnt = 0

for r in list(itertools.permutations(R)):
    l = 0
    for i in range(N-1):
        l += ((X[r[i]] - X[r[i+1]])**2 + (Y[r[i]] - Y[r[i+1]])**2)**0.5
    L += l
    cnt += 1

print(L/cnt)

Solution (Python):
import itertools

n=int(input())
listposi= []
order = []
for i in range(n):
    tmp = [int(j) for j in input().split()]
    listposi.append(tmp)
    order.append(i)
    

olist = list(itertools.permutations(order))


dist = 0
for test in olist:
    for i in range(n-1):
        sta = test[i]
        gol = test[i+1]
        stax = listposi[sta][0]
        stay = listposi[sta][1]
        golx = listposi[gol][0]
        goly = listposi[gol][1]
        dist += ((stax-golx)**2+(stay-goly)**2)**0.5
print(dist/len(olist))

Solution (Python):
from itertools import permutations
from math import sqrt,factorial
n=int(input())
p=[tuple(map(int,input().split(' '))) for j in range(n)]
al = factorial(n)
ans = 0
l= [i for i in range(n)]
l=permutations(l)
for i in l:
    tmp = 0
    for j in range(n-1):
        tmp += sqrt((p[i[j]][0]-p[i[j+1]][0])**2+(p[i[j]][1]-p[i[j+1]][1])**2)
    ans += tmp/al
print(ans)

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

import itertools

arr = []

for i in range(n):
    arr.append(list(map(int,input().split())))


ptr = list(itertools.permutations(arr, n))


dis = 0

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

Solution (Python):
n = int(input())
town = []

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

ans = 0
for i in range(n):
    x1, y1 = town[i]
    for j in range(n):
        if j == i:
            continue
        x2, y2 = town[j]
        dist = ((x1 - x2)**2 + (y1 - y2)**2) ** 0.5
        ans += dist

ans /= n
print(ans)

Solution (Python):
import math
def f(a,b):
    c = (a[0]-b[0])**2 + (a[1]-b[1])**2
    return math.sqrt(c)
n = int(input())
l = []
x = 0
for _ in range(n):
    l.append(list(map(int,input().split())))
for i in range(0,n-1):
    for j in range(i+1,n):
        x = x + f(l[i],l[j])
print((2*x)/n)

Solution (Python):

import math
import itertools

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

ave = float(0)
cnt = 0
for r in itertools.permutations(l):
    tmp = float(0)
    for i in range(N-1):
        tmp += math.sqrt(((r[i][0] - r[i+1][0])**2) + ((r[i][1] - r[i+1][1])**2))
    ave += tmp
    cnt += 1
print(ave/cnt)

Solution (Python):
import itertools
import math
def dist(c1,c2):
  return math.sqrt((c1[0]-c2[0])**2+(c1[1]-c2[1])**2)
n = int(input())
cities = {}
s = 0
for i in range(n):
  cities[i] = list(map(int,input().split()))
lis = [x for x in range(n)]
for junjo in itertools.permutations(lis):
  for i in range(len(junjo)-1):

    s += dist(cities[junjo[i]],cities[junjo[i+1]])
print(s/math.factorial(n))

Solution (Python):
import itertools
import math
N = int(input())
sm = 0
xy= [list(map(int, input().split())) for _ in range(N)]
L = itertools.permutations(list(range(N)),N)
for l in L:
    for i in range(len(l)-1):
        sm += ((xy[l[i]][0]-xy[l[i+1]][0])**2+(xy[l[i]][1]-xy[l[i+1]][1])**2)**0.5

print(sm / math.factorial(N))

Solution (Python):
from itertools import permutations

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

def d(xy1, xy2):
    return ((xy1[0] - xy2[0])**2 + (xy1[1] - xy2[1])**2)**0.5

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

s, e = 0, 1
ds = []
for i in p:
    while e <= n-1:
        xy1 = i[s]
        xy2 = i[e]
        ds.append(d(xy1, xy2))
        s += 1
        e += 1
    s, e = 0, 1

print(sum(ds)/len(p))

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

mylist =[]

for i in range(N):
    myx , myy = map(int, input().split())
    mylist += [[myx, myy]]
    


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

print((mysum*2)/(N))

Solution (Python):
import math

def main():

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

    f = 1
    for i in range(1, N+1): f *= i
    dist = [[0 for _ in range(N)] for _ in range(N)]
    d = 0
    for i in range(N):
        for j in range(N):
            dist[i][j] = math.sqrt(pow(p[i][0]-p[j][0], 2) + pow(p[i][1]-p[j][1], 2))
            d += dist[i][j]
    return d / N

if __name__ == '__main__':
    print(main())

Solution (Python):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline






















def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N = inputInt()
	xy = []
	seq = []

	for i in range(N):
		x,y = inputMap()
		xy.append((x,y))
		seq.append(i)

	ptns = list(itertools.permutations(seq))

	anss = []
	for ptn in ptns:
		ptn_list = list(ptn)

		strt = 0
		for i,val in enumerate(ptn_list):
			if i == 0:
				strt = val
				continue

			stx, sty = xy[strt]
			sdx, sdy = xy[val]
			tmptmp = ((stx-sdx)**2) + ((sty-sdy)**2)
			tmp = math.sqrt(tmptmp)
			anss.append(tmp)

	ans = 0
	for i in anss:
		ans += i

	print(ans/len(ptns))




if __name__ == "__main__":
	main()

Solution (Python):
from itertools import combinations
def d(x1,x2):
    return ((x1[0]-x2[0])**2+(x1[1]-x2[1])**2)**0.5
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
tot = 0
for x in combinations(range(N),2):
    tot += d(A[x[0]],A[x[1]])
print(2*tot/N)

Solution (Python):
import itertools
N = int(input())
lst = []
for i in range(N):
    x, y = map(int, input().split())
    lst.append([x, y])
dist = list(itertools.permutations(lst))
ans = []
for i in range(len(dist)):
    a = 0
    for j in range(N-1):
        a += ((dist[i][j][0]-dist[i][j+1][0])**2+(dist[i][j][1]-dist[i][j+1][1])**2)**0.5
    ans.append(a)
print(sum(ans)/len(ans))

Solution (Python):
N =int(input())
xy = [list(map(int,input().split())) for i in range(N)]
from itertools import permutations
res = []
for i in permutations(range(N)):
  s = 0
  for j in range(len(i)-1):
    xa,ya = xy[i[j]]
    xb,yb = xy[i[j+1]]
    s += ((xa-xb)**2+(yb-ya)**2)**(1/2)
  res += [s]
print(sum(res)/len(res))

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

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

from itertools import permutations

res = 0
cnt = 0

for lst in permutations([i for i in range(n)], n):
    r = 0
    cnt += 1
    for i in range(n - 1):
        t1 = towns[lst[i]]
        t2 = towns[lst[i - 1]]
        r += ((t1[0] - t2[0]) ** 2 + (t1[1] - t2[1]) ** 2) ** 0.5

    res += r

print(res / cnt)