Problem:


Score : 300 points

Problem Statement

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

There are N! possible paths to visit all of these towns once. Let the length of a path be the distance covered when we start at the first town in the path, visit the second, third, \dots, towns, and arrive at the last town (assume that we travel in a straight line from a town to another). Compute the average length of these N! paths.

Constraints

2 \leq N \leq 8

-1000 \leq x_i \leq 1000

-1000 \leq y_i \leq 1000

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

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

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

Print the average length of the paths.
Your output will be judges as correct when the absolute difference from the judge's output is at most 10^{-6}.

Sample Input 1

3
0 0
1 0
0 1

Sample Output 1

2.2761423749

There are six paths to visit the towns: 1 → 2 → 3, 1 → 3 → 2, 2 → 1 → 3, 2 → 3 → 1, 3 → 1 → 2, and 3 → 2 → 1.

The length of the path 1 → 2 → 3 is \sqrt{\left(0-1\right)^2+\left(0-0\right)^2} + \sqrt{\left(1-0\right)^2+\left(0-1\right)^2} = 1+\sqrt{2}.

By calculating the lengths of the other paths in this way, we see that the average length of all routes is:

\frac{\left(1+\sqrt{2}\right)+\left(1+\sqrt{2}\right)+\left(2\right)+\left(1+\sqrt{2}\right)+\left(2\right)+\left(1+\sqrt{2}\right)}{6} = 2.276142...

Sample Input 2

2
-879 981
-866 890

Sample Output 2

91.9238815543

There are two paths to visit the towns: 1 → 2 and 2 → 1. These paths have the same length.

Sample Input 3

8
-406 10
512 859
494 362
-955 -475
128 553
-986 -885
763 77
449 310

Sample Output 3

7641.9817824387



Sample input:
3
0 0
1 0
0 1


Sample output:
2.2761423749

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import numpy as np
import itertools

N = int(input())
xs = np.zeros(N)
ys = np.zeros(N)
for i in range(N):
  xs[i], ys[i] = map(int, input().split())

lenMat = np.zeros((N, N))
for j in range(N):
  for i in range(N):
    lenMat[j,i] = np.sqrt((xs[i]-xs[j])**2 + (ys[i]-ys[j])**2)

sumVal = 0.0     
count = 0

seq = np.arange(N)
for lst in list(itertools.permutations(seq)):
    #print(lst)
    count += 1
    for i in range(N-1):
	    sumVal += lenMat[lst[i], lst[i+1]] 

print(sumVal/count)
        
        
#for i in range(N):
#  print(xs[i],ys[i])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
X=[0 for i in range(N)]
Y=[0 for i in range(N)]
for i in range(N):
  X[i],Y[i]=map(int,input().split())
Sum=0
for i in range(N):
  for p in range(N):
    Sum+=((X[i]-X[p])**2+(Y[i]-Y[p])**2)**(1/2)
print(Sum/N)

Submission status: Accepted

Solution code:
import math

n = int(input())

x = []
y = []

x_dis = 0
y_dis = 0
total_dis = 0

for i in range(n):
    x1, y1 = map(int, input().split())
    x.append(x1)
    y.append(y1)

for i in range(n):
    for j in range(n):
        if i == j:
            continue
        x_dis = (x[i] - x[j]) ** 2
        y_dis = (y[i] - y[j]) ** 2
        total_dis += math.sqrt(x_dis + y_dis)

print(total_dis / n)

Submission status: Accepted

Solution code:
import sys
import itertools
import numpy as np

lines = sys.stdin.readlines()

N = int(lines[0].rstrip())
perms = list(itertools.permutations(range(N)))
combs = list(itertools.combinations(range(N), 2))

arr_2d = np.zeros((N,2))
if N <= 2:
	arr_dist_memo = np.zeros((len(combs)+1,len(combs)+1))
else:
	arr_dist_memo = np.zeros((len(combs),len(combs)))

arr_dist_ave = np.zeros(len(perms))

for i, line in enumerate(lines[1:]):
    x, y = map(int,line.split(' '))
    arr_2d[i, 0] = x
    arr_2d[i, 1] = y

for i,j in combs:
    arr_dist_memo[i, j] = np.linalg.norm(arr_2d[i] - arr_2d[j])

for index, l in enumerate(perms):
    for i, j  in zip(range(N-1), range(1, N)):
        arr_dist_ave[index] += arr_dist_memo[l[i],l[j]]

print(np.mean(arr_dist_ave)*2)

Submission status: Accepted

Solution code:
import math
def calc(now,points,length,M,ans):
  if len(points)==0:
    #print(length).
    ans.append(length)
    return 0
  for i in range(len(points)):
    #print(points,points[:i]+points[i+1:])
    tmp=length + math.sqrt( ((now[0]-M[points[i]][0])**2) + ((now[1]-M[points[i]][1])**2) )
    #print(tmp)
    #return length + calc(M[points[i]],points[:i]+points[i+1:],tmp,M)
    calc(M[points[i]],points[:i]+points[i+1:],tmp,M,ans)
n=int(input())
M=[]
for i in range(n):
  M.append(list(map(int,input().split())))
ans=[]
points=[]
num=1
for i in range(n):
  points.append(i)
  num=num*(i+1)
for i in range(n):
  #print(i,points[:i]+points[i+1:])
  #ans.append(calc(M[i],points[:i]+points[i+1:],0.0,M))
  calc(M[i],points[:i]+points[i+1:],0.0,M,ans)
#print(ans)
print(sum(ans)/num)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
import numpy as np

n = int(input())
cood = [tuple(map(int, input().split())) for _ in range(n)]
distances = np.zeros((n, n))
for i in range(n):
    for j in range(n):
        dx = cood[i][0] - cood[j][0]
        dy = cood[i][1] - cood[j][1]
        distances[i][j] = math.sqrt(dx*dx + dy*dy)

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

dup = fact / n
total = np.sum(distances * dup)
ave = total / fact
print(ave)

Submission status: Accepted

Solution code:
def main():
    pointers = int(input())
    points = []
    for i in range(pointers):
        points.append(input().split())
    
    distances = 0
    distances_len = 0

    search_point = 0
    target_point = 1

    for i in range(search_point, pointers):
        for j in range(target_point, pointers):
            distances_len += 1
            distance = ((int(points[i][0]) - int(points[j][0])) ** 2 + (abs(int(points[i][1]) - int(points[j][1]))) ** 2) ** 0.5
            distances += distance
        target_point += 1

    print(distances / distances_len * (pointers - 1))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

N = int(input())
x = [None]*N
y = [None]*N
for i in range(N):
    x[i], y[i] = [int(j) for j in input().split(' ')]

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


def a(j, N):
    s = 0
    if len(j)==N:
        for i in range(len(j)-1):
            s+=distance(x[j[i]], y[j[i]], x[j[i+1]], y[j[i+1]])
        return s
    for i in range(N):
        j2 = j[:]
        if i in j2:
            continue
        j2.append(i)
        s += a(j2, N)
    return s

print(a([], N)/math.factorial(N))

Submission status: Accepted

Solution code:
import math

N = int(input())
list = []
for i in range(N):
    n = input()    
    m = n.split()
    p = [int(i) for i in m]
    list.append(p)
dis = 0
while list != []:
    for a in list:
        d = (a[0] - list[0][0]) ** 2 + (a[1] - list[0][1]) ** 2
        trued = d ** 0.5
        dis = dis + trued
    else:
        list = [] + list[1:]
else:
    dis = dis * 2 / N
    print(dis)

Submission status: Accepted

Solution code:
n = int(input())
x = []
y = []
list = []
ans = 0
for i in range(n):
  x0, y0 = input().split()
  x.append(int(x0))
  y.append(int(y0))
for i in range(n):
  for j in range(n):
    list.append(((x[i] - x[j])**2 + (y[i] - y[j])**2)**0.5)
print(sum(list)/len(x))

Submission status: Accepted

Solution code:
n = int(input())

towns = []
count = 0
lenSum = 0

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

for p in range(len(towns)-1) :
    for q in range(p+1, len(towns)) :
        lenSum += ((towns[p][0] - towns[q][0]) ** 2 + (towns[p][1] - towns[q][1]) ** 2) ** 0.5
        count += 1

print(lenSum / count * (n - 1))

Submission status: Accepted

Solution code:
from itertools import permutations
import math

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

    
n_root = 0
dist = []
for r in permutations(range(N)):
    # print(r)
    curr_dist = []
    for i in range(1,N):
        curr_dist.append(math.sqrt(\
           (xy[r[i]][0] - xy[r[i-1]][0])**2 +\
           (xy[r[i]][1] - xy[r[i-1]][1])**2
           ))
    dist.append(sum(curr_dist))
    n_root += 1
    # break
    
print(sum(dist)/n_root)

Submission status: Accepted

Solution code:
# 2019-11-16 21:01:15(JST)
import sys
# import collections
import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

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

def main():
    n = int(sys.stdin.readline().rstrip())
    x, y = [], []
    for _ in range(n):
        xi, yi = [int(x) for x in sys.stdin.readline().split()]
        x.append(xi)
        y.append(yi)

    ans = 0
    for p in itertools.permutations(range(n), n):
        d = 0
        for i in range(n-1):
            d += dist(x[p[i]], y[p[i]], x[p[i+1]], y[p[i+1]])
        ans += d
    
    ans /= math.factorial(n)
    print(ans)

  
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
import itertools

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

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

p_list = list(itertools.permutations(di, n))
total_dist = 0
total_count = 0

for c in p_list:
    dist = 0
    src = c[0]
    for ci in range(1, n):
        dst = c[ci]
        dist += d[src][dst]
        if(ci != n-1):
            src = dst
    total_dist += dist
    total_count += 1

print(total_dist/total_count)

Submission status: Accepted

Solution code:
import numpy as np

def abc(num):
    ret = 1
    for i in range(1,num+1):
        ret *= i
    #print(num,ret)
    return ret

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

tmp = (n-1) * (abc(n-1)) / (abc(n-1)+(n-1))
tmp = (tmp * 2 + tmp * 2 * (abc(n-2))) / (abc(n))

ans = 0

for i in range(n):
    for j in range(i+1,n):
        ans += np.sqrt((x[i]-x[j]) **2 + (y[i]-y[j]) **2)
print(ans * tmp)

Submission status: Accepted

Solution code:
import math
N = int(input())
coordinates = []
total_distance = 0
for i in range(N):
    x,y = map(int,input().split())
    coordinates.append([x,y])
    
for j in range(N):
    start = coordinates[j]
    for k in range(N):
        if k == j:
            continue
        else:
            end = coordinates[k]
            distance = math.sqrt((end[0]-start[0])**2+(end[1]-start[1])**2)
            total_distance += distance
tmp = 2            
for l in range(2,N):
     tmp *=l
ans = tmp*total_distance/(2*math.factorial(N))
print(ans)

Submission status: Accepted

Solution code:
import math

N = int(input())

X = [0]*N
Y = [0]*N

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

ans = 0

for i in range(N-1):
    for j in range(i, N):
        ans += math.sqrt((X[i]-X[j])**2+(Y[i]-Y[j])**2)


print(ans * 2 / N)

Submission status: Accepted

Solution code:
import math
N = int(input())
X = []
Y = []
for i in range(N):
    x,y = map(int,input().split())
    X.append(x)
    Y.append(y)
    
length = []
for i in range(N-1):
    for j in range(i+1, N):
        tmp = math.sqrt((X[i] - X[j])**2 + (Y[i] - Y[j])**2)
        length.append(tmp)
path = 0
for i in range(N):
  path += i
res = 0
for i in range(path):
  res += length[i]
fac = math.factorial(N)
total = fac * (N-1) /path
res *= total
res /= fac
print(res)

Submission status: Accepted

Solution code:
import math


def kyori(list_a,list_b):
    return math.sqrt((list_a[0] - list_b[0]) ** 2 + (list_a[1] - list_b[1]) ** 2)


def sum_kyori(n,n_paths):
    result = 0
    for i in range(n):
        for j in range(n):
            if j>i:
                result = result+kyori(n_paths[i],n_paths[j])
    return result


n = int(input())
paths = []
for i in range(n):
    paths.append(list(map(lambda x:int(x),input().split(" "))))


print(sum_kyori(n,paths)*2/n)

Submission status: Accepted

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

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

c = sum(b)
d = c * (N-1) / (N*(N-1)/2)
print(d)

Submission status: Accepted

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

import math, itertools, statistics

res = []
for v in itertools.permutations(range(N), N):
	d = []
	for i in range(N-1):
		d.append(
			math.sqrt((x[v[i]]-x[v[i+1]])**2 + (y[v[i]]-y[v[i+1]])**2))
	res.append(sum(d))
print(statistics.mean(res))

Submission status: Accepted

Solution code:
import math

def distance(a, b, c, d):
    return math.sqrt(((a - b) ** 2) + ((c - d) ** 2))

N = int(input())

xy = []
for i in range(N):
    tmp = list(map(int, input().split()))
    xy.append(tmp)
    
sum_dis = 0
dis_list = []
for i in range(N-1):
    for j in range(i+1, N):
        dis_list.append(distance(xy[i][0], xy[j][0], xy[i][1], xy[j][1]))


print(sum(dis_list) * (math.factorial(N-1)*2) / (math.factorial(N)))

Submission status: Accepted

Solution code:
N=int(input())

import numpy as np

cord = []

for n in range(N):
    str_list = input().split(' ')
    int_list = [int(x) for x in str_list]
    cord.append(int_list)

cord = np.array(cord)
cord_tile = np.tile(cord, (1,N))
cord_tile_ = np.reshape(cord_tile, (len(cord_tile), len(cord_tile), 2))
cord_tile_t = np.transpose(cord_tile_.copy(),(1,0,2) )


dist_mat = np.sqrt( np.sum( (cord_tile_-cord_tile_t)**2, axis=2) )

import math
facto = math.factorial(N-1)

print( np.sum(dist_mat)/N )

Submission status: Accepted

Solution code:
import heapq as h
import math
import numpy as np
import copy
import itertools

 
# n,m = map(int,input().split())
n = int(input())
# l = list(map(lambda x:-int(x),input().split()))
ll = []
for _ in range(n):
    ll.append(list(map(int, input().split())))
dis = []
sum = 0
for v in itertools.permutations(ll, n):
    for i in range(n-1):
        sum += math.sqrt((v[i][0] - v[i+1][0])**2 + (v[i][1]-v[i+1][1])**2)

    

    # dis.append(math.sqrt((v[0][0] - v[1][0])**2 + (v[0][1]-v[1][1])**2))
print(sum/math.factorial(n))

# sum = 0
# for i,v in enumerate(itertools.permutations(dis, n-1)):
#     sum += v[0] + v[1]
# print(sum/len(dis))
# print(dis)

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt
N = int(input())
Ps = [list(map(int, input().split())) for _ in range(N)]
ans = 0
for L in permutations(Ps):
    for i in range(1, N):
        ans += sqrt(pow(L[i][0]-L[i-1][0],2) + pow(L[i][1]-L[i-1][1],2))

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

Submission status: Accepted

Solution code:
import math
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
d=0
for i in range(n):
  for j in range(n):
    if i==j:
      continue
    d+=math.sqrt((xy[i][0]-xy[j][0])**2+(xy[i][1]-xy[j][1])**2)
print(d/n)

Submission status: Accepted

Solution code:
from math import sqrt, factorial


def solve():
    N = int(input())
    xy_l = [[0, 0] for _ in range(N)]
    for i in range(N):
        xy_l[i] = list(map(int, input().split()))
    distance_l = []

    for i in range(N-1):
        for j in range(i+1, N):
            distance_l.append(sqrt((xy_l[i][0]-xy_l[j][0])**2 + (xy_l[i][1]-xy_l[j][1])**2))
    print(sum(distance_l)*2*factorial(N-1)/factorial(N))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import math

def leng(ax,ay,bx,by):
    aa=ax-bx
    bb=ay-by
    return (aa*aa+bb*bb)**0.5

def main():
    n=int(input())
    x = [0] * n
    y = [0] * n
    for i in range(n):
        x[i], y[i] = map(int, input().split())
        cnt=0.0
    for i in range(0,n):
        for j in range(i+1,n):
            cnt+=leng(x[i],y[i],x[j],y[j])
    cnt/=n
    print(cnt*2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
n = int(input())
X = []
Y = []
for i in range(n):
    x,y = map(int,input().split())
    X.append(x)
    Y.append(y)
sum = 0
D = []

for i in range(n):
    for j in range(n):
        d = math.sqrt((X[i]-X[j])**2 + (Y[i]-Y[j])**2)
        sum+=d

ave = sum/n
print(ave)

Submission status: Accepted

Solution code:
ans = 0
def solve():
    n = int(input())
    XY = [list(map(int, input().split())) for _ in range(n)]
    def f(a, b, kyori, li):
        if b == (1 << n) - 1:
            global ans
            ans += kyori
            return
        for i in range(n):
            if not ((b >> i) & 1):
                t = ((XY[a][0] - XY[i][0]) ** 2 + (XY[a][1] - XY[i][1]) ** 2) ** .5
                f(i, b | (1 << i), kyori + t, li + [i])
    for i in range(n):
        f(i, 1 << i, 0, [i])
    def g(a):
        ret = a
        for i in range(2, a):
            ret *= i
        return ret
    print(ans / g(n))
solve()

Submission status: Accepted

Solution code:
import itertools
from math import *
n = int(input())

x = [0]*n
y = [0]*n

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


per = list(itertools.permutations(range(n)))
d = [[0 for i in range(n)] for j in range(n)]

for i in range(n):
    for j in range(n):
        if i != j:
            d[i][j] = sqrt(abs(x[i]-x[j])**2 + abs(y[i]-y[j])**2)
        else:
            d[i][j] = 0;
ans = 0

for road in per:
    for k in range(n-1):
        ans += d[road[k]][road[k+1]]


print(ans/factorial(n))

Submission status: Accepted

Solution code:
N = int(input())

P = []

S = 0

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

for i in range(N-1):
    for j in range(N-1-i):
        
        S += (((P[i][0] - P[i+j+1][0])**2 + (P[i][1] - P[i+j+1][1])**2)**0.5)*2
        
print(S/N)

Submission status: Accepted

Solution code:
N = int(input())
xy = []
for _ in range(N):
  x, y = map(int, input().split())
  xy.append([x, y])
import itertools
from math import sqrt
distance = 0
perm = list(itertools.permutations(xy))
for P in perm:
  for i in range(N):
    if i == N - 1:
      break
    diff = sqrt((P[i][0] - P[i + 1][0]) ** 2 + (P[i][1] - P[i + 1][1]) ** 2)
    distance += diff
print(distance / len(perm))

Submission status: Accepted

Solution code:
import numpy as np
import statistics
import itertools

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


p = 0
for v in itertools.permutations(ls, n):
    al.append(v)
    
for i in range(len(al)):
    ans = 0
    for j in range(n-1):
        ans += np.sqrt((al[p][j+1][0]-al[p][j][0])**2+(al[p][j+1][1]-al[p][j][1])**2)
    al2.append((ans))
    p += 1
    
print(sum(al2)/len(al2))

Submission status: Accepted

Solution code:
N = int(input())
X = []
for i in range(N):
    X.append([int(i) for i in input().split(' ')])
    
import itertools
import math
Length = 0
for root in itertools.permutations(range(N)):
    length = 0
    
    for city in root:
        city_now = city
        if root.index(city) >0:
            length += math.sqrt(
                (X[city_now][0]-X[city_before][0])**2+(X[city_now][1]-X[city_before][1])**2)

        city_before = city
    Length += length
print(Length/math.factorial(N))

Submission status: Accepted

Solution code:
import itertools
import math

n = int(input())

allList = []

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

long = 0
for i in itertools.permutations(allList):
    old = []
    for j in i:
        if (old == []):
            old = j
        else:
            long = long + pow(pow((old[0] - j[0]), 2) +pow((old[1] - j[1]), 2), 0.5)
            old = j

print(long / math.factorial(n))

Submission status: Accepted

Solution code:
import itertools
num = int(input())
xlist = []
ylist = []
plist = []
for i in range(0,num):
  list = input().split(" ")
  xlist.append(int(list[0]))
  ylist.append(int(list[1]))

for t in itertools.permutations(range(num)):
  plist.append(t)
sum = 0
for n1 in range(0,len(plist)):
  S = 0
  sx = xlist[plist[n1][0]]
  sy = ylist[plist[n1][0]]
  for n2 in range(1,num):
    l = ((sx-xlist[plist[n1][n2]])**(2)+(sy-ylist[plist[n1][n2]])**(2))**(1/2)
    S += l
  sum += S
print(sum/len(plist))

Submission status: Accepted

Solution code:
import itertools
import math
I = [int(_) for _ in open(0).read().split()]
N = I[0]
X, Y = I[1::2], I[2::2]
ans = 0
for root in itertools.permutations(range(N), N):
    for a, b in zip(root, root[1:]):
        ans += ((X[a] - X[b])**2 + (Y[a] - Y[b])**2)**0.5
ans /= math.factorial(N)
print(ans)

Submission status: Accepted

Solution code:
import math
total_sum = 0
def calculate_sum(n,coords,appender):
	i=0
	dist = 0
	while i<n-1:
		first = appender[i]
		second = appender[i+1]
		dist += math.sqrt((coords[first][0]-coords[second][0])**2+(coords[first][1]-coords[second][1])**2)
		i+=1
	return dist


def factorial(n,coords,nos,appender,flag):
	if nos==n:
		global total_sum
		total_sum += calculate_sum(n,coords,appender)
		#print(total_sum)
		return
	else:
		for i in range(n):
			if i not in flag:
				flag.append(i)
				appender.append(i)
				factorial(n,coords,nos+1,appender,flag)
				flag.pop()
				appender.pop()
		return

n = int(input())
coords = [[0]*2 for i in range(n)]
for i in range(n):
	coords[i][0],coords[i][1] = map(int,input().split())
the_nos_fact = 1
for i in range(2,n+1):
	the_nos_fact*=i
factorial(n,coords,0,[],[-1])
print(total_sum/the_nos_fact)

Submission status: Accepted

Solution code:
# coding: utf-8
import itertools
import math


def solve(*args: str) -> str:
    n = int(args[0])
    XY = [tuple(map(int, xy.split())) for xy in args[1:]]

    ret = 0

    for P in itertools.permutations([i for i in range(n)], n):
        for i in range(1, n):
            xs, ys = XY[P[i-1]]
            xd, yd = XY[P[i]]
            ret += math.sqrt((xs-xd)**2+(ys-yd)**2)

    ret /= math.factorial(n)
    # return '{:.10f}'.format(ret)
    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

Solution code:
import itertools
import math

N = int(raw_input())

pts = [map(float, raw_input().split()) for _ in xrange(N)]

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

def path_len(path):
    return sum(dist(path[i-1], path[i]) for i in xrange(1, len(path)))

total_cnt = 0
total_len = 0.
for path in itertools.permutations(pts):
    total_len += path_len(path)
    total_cnt += 1

print total_len/total_cnt

Submission status: Accepted

Solution code:
import copy

def patterns(n):
    if(n==2):
        return [[0,1],[1,0]]
    else:
        a = patterns(n-1)
        new = []
        for i in a:
            for j in range(n):
                copied = copy.copy(i)
                copied.insert(j,n-1)
                new.append(copied)
        return new

N = int(input())
X = []
Y = []
for i in range(N):
    p = input().split()
    X.append(int(p[0]))
    Y.append(int(p[1]))

lengthsum = 0.0
pattern = patterns(N)
for i in pattern:
    for j in range(N-1):
        lengthsum += ((X[i[j+1]]-X[i[j]])**2+(Y[i[j+1]]-Y[i[j]])**2)**0.5

print(lengthsum/len(pattern))

Submission status: Accepted

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

import itertools
NP=list(itertools.permutations(range(N)))

a=[[0]*(len(NP[0])-1) for i in range(len(NP))]
for i in range(len(NP[0])-1):
    for j in range(len(NP)):
        a[j][i] = ((xy[int(NP[j][i])][0]-xy[int(NP[j][i+1])][0])**2 + (xy[int(NP[j][i])][1]-xy[int(NP[j][i+1])][1])**2)**0.5

b=[0]*(len(a))
for i in range(len(a)):
    b[i]=sum(a[i])

print(sum(b)/len(b))

Submission status: Accepted

Solution code:
from itertools import permutations
import numpy as np

def calc_distance(point):
    _point = np.array(list(point))
    x = np.diff(_point, axis=0)
    every_distance = np.linalg.norm(x, axis=1)
    all_distance = np.sum(every_distance)
    return all_distance

n = int(input())
points = [[int(v) for v in input().split(' ')] for _ in range(n)]

sum = 0
for v in permutations(points):
    sum += calc_distance(v)


print(sum / len(list(permutations(points))))

Submission status: Accepted

Solution code:
import math
import itertools

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

l = list(range(1,N+1))

kai_list = list(itertools.permutations(l))

result = 0
count = 0

for item_i in kai_list:
    for i in range(1,len(item_i)):
        result += math.sqrt((X[item_i[0]-1] - X[item_i[i]-1])**2 + (Y[item_i[0]-1] - Y[item_i[i]-1])**2)

count = len(kai_list)
print(result/count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import math
import itertools

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

total = []
seq = list(itertools.permutations(range(len(x))))

for i in range(len(seq)):
    dist = 0
    seq_prev = None
    for j in seq[i]:
        if(seq_prev is not None):
            dist += (math.sqrt((x[j] - x[seq_prev]) ** 2 + (y[j] - y[seq_prev]) ** 2))
        seq_prev = j
    total.append(float(dist))

print(sum(total) / len(total))

Submission status: Accepted

Solution code:
import math

N = int(input())

xy_dict = {}
tmp =[0]
for i in range(N):
    x, y = map(float, input().split())
    #print(x)
    #print(y)

    xy_dict[i] = (x,y)
#print(xy_dict)
#print(xy_dict[0][0])
#print(xy_dict[0][1])

distance_list = []

for i in range(N):
    for j in range(i+1, N):
        x1 = xy_dict[i][0]
        y1 = xy_dict[i][1]
        x2 = xy_dict[j][0]
        y2 = xy_dict[j][1]
        a = math.sqrt((x1 - x2)**2 + (y1 - y2)**2)
        distance_list.append(a)
        #print("i,j is ", i,j)

sum = 0
for i in range(len(distance_list)):
    sum += distance_list[i]
        
print(math.factorial(N-1) * 2* sum/(math.factorial(N)))

Submission status: Accepted

Solution code:
import itertools
import math

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

a = list(itertools.permutations(range(n), n))

D = 0
for _ in a:
    for s in range(n -1):
        c = _[s]
        c1 = _[s+1]
        X = (x[c] - x[c1])**2
        Y = (y[c] - y[c1])**2
        r =  math.sqrt(X+Y)
        D += r
print(D / len(a))

Submission status: Accepted

Solution code:
import  math
N=int(input())
Towns=[]
distance=0
for i in range(N):
    tmp=input().split()
    Towns.append([int(tmp[0]),int(tmp[1])])

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

print(2*distance/N)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
import math

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

for Root in list(itertools.permutations(cities)):
  xi, yi = Root[0][0], Root[0][1]
  for xj, yj in Root[1:]:
    total_length += np.sqrt((xi - xj)**2 + (yi - yj)**2)

print(total_length / math.factorial(N))

Submission status: Accepted

Solution code:
import math
n = int(input())
x = []
y = []
for i in range(n):
    x1, y1 = (int(j) for j in input().split())
    x.append(x1)
    y.append(y1)
l = 0
ave = 0
for i in range(n):
    for j in range(n):
        if i>j:
            dx = abs(x[i]-x[j])
            dy = abs(y[i]-y[j])
            l += float(math.sqrt(dx**2 + dy**2))
ave = 2*l/(n*(n-1))
ans = ave * (n-1)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
p = [list(map(int, input().split())) for _ in range(n)]
def distances(x1,x2,y1,y2):
    return ((x2-x1)**2+(y2-y1)**2)**0.5

td =0
for i in range(n):
    for j in range(n):
        if i != j :
            td += distances(p[i][0],p[j][0],p[i][1],p[j][1])

a =1
for i in range(1,n+1):
    a = a*i
print(td/n)

Submission status: Accepted

Solution code:
import itertools
import math

n = int(input())
x = [0] * n
y = [0] * n

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


def solve():
    patterns = list(itertools.permutations(range(n)))

    sum_ans = []

    for pattern in patterns:
        tmp_ans = []
        for j in range(n - 1):
            now_city = pattern[j]
            next_city = pattern[j + 1]
            tmp = (x[now_city] - x[next_city]) ** 2 + (y[now_city] - y[next_city]) ** 2
            tmp_ans.append(
                math.sqrt(tmp)
            )
        sum_ans.append(
            sum(tmp_ans)
        )

    return sum(sum_ans) / len(patterns)


print(solve())

Submission status: Accepted

Solution code:
import math

n=int(input())
machi=[]
for i in range(n):
    temp1,temp2=map(int,input().split())
    machi.append([temp1,temp2])

#print(machi)

bai=math.factorial(n-2)

sum=0

for i in range(n):
    for j in range(n):
        if(i==j):
            continue
        nijou=(machi[i][0]-machi[j][0])**2+(machi[i][1]-machi[j][1])**2
        kyori=nijou**(1/2)
        sum+=kyori*bai

print((n-1)*sum/math.factorial(n))

Submission status: Accepted

Solution code:
import itertools
import math

N = int(input())
x = []
y = []
for i in range(N):
    X,Y = map(int,input().split())
    
    x.append(X)
    y.append(Y)
n = math.factorial(N)
c = list(zip(x,y))
cnt = 0
x_list = []
y_list = []
for i in itertools.permutations(c):
    mm = i
    for k in range(N):
        x_list.append(mm[k][0])
        y_list.append(mm[k][1])
    for f in range(N-1):
        cnt += math.sqrt((x_list[f+1]  - x_list[f])**2 + (y_list[f+1] - y_list[f] ) ** 2)
    x_list = []
    y_list = []
print(cnt / n)

Submission status: Accepted

Solution code:
import numpy as np
import math
N = int(input())
a = list()
for i in range(N):
    a.append(list(map(int, input().split())))
a = np.array(a)    
dis = 0
for i in range(N):
    for j in range(N):
        dis = dis + math.sqrt((a[i][0]-a[j][0])**2+(a[i][1]-a[j][1])**2)
dis = dis/2
print(dis*2/N)

Submission status: Accepted

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

n = int(stdin.readline().rstrip())
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]

lis = []
lin = list(permutations(li,n))

for i in range(len(lin)):
    liv = []
    for j in range(1,len(lin[0])):
        a = (lin[i][j-1][1]-lin[i][j][1])**2
        b = (lin[i][j-1][0]-lin[i][j][0])**2
        c = math.sqrt(a+b)
        liv.append(c)
    lis.append(sum(liv))
print(sum(lis)/len(lin))

Submission status: Accepted

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

Submission status: Accepted

Solution code:

import itertools, math

x=[]

n=int(input())

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

p = itertools.permutations(x, n)

def dif(x, y):
 return math.sqrt((x[0]-y[0])**2+(x[1]-y[1])**2)

l=[]

for z in p:
  for i in zip(z[1:],z[:-1]):l.append(dif(i[0],i[1]))

print (sum(l)/math.factorial(len(z)))