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:
import itertools

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

zerotoN = ""
for i in range(0,N):
    zerotoN += str(i)
keiro_list = list(itertools.permutations(zerotoN))

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

all_sum = 0

for keiro in keiro_list:
    for i in range(N-1):
        x1 = XY[int(keiro[i])][0]
        y1 = XY[int(keiro[i])][1]
        x2 = XY[int(keiro[i+1])][0]
        y2 = XY[int(keiro[i+1])][1]
        all_sum += ((x1-x2)**2 + (y1-y2)**2)**0.5

keiro_num = len(keiro_list)
print(all_sum/keiro_num)

Submission status: Accepted

Solution code:
import itertools
import math
ans = 0
l = []

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

for i in itertools.permutations(xy, n):
    l.append(i)
    for j in range(n - 1):
        ans += math.sqrt((i[j + 1][0] - i[j][0]) ** 2 +\
        (i[j + 1][1] - i[j][1]) ** 2)

ans /= len(l)
print(ans)

Submission status: Accepted

Solution code:
import itertools

n = int(input())

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

total = 0

for x1, y1 in xy:
    for x2, y2 in xy:
        total += ((x1 - x2)**2 + (y1 - y2)**2)**(1/2)
    
print(total/n)

Submission status: Accepted

Solution code:
from itertools import combinations

n = int(input())
D = []
ans = 0
for i in range(n):
    x,y = map(int,input().split())
    D.append((x,y))
for i,j in combinations(range(1,n+1),r=2):
    p,q = D[i-1]
    r,s = D[j-1]
    ans += ((p-r)**2+(q-s)**2)**(0.5)
print(2*ans/n)

Submission status: Accepted

Solution code:
import itertools as it
import math
from statistics import mean
N=int(input())
X=[list(map(int,input().split())) for i in range(N)]
A=[]
for i in list(it.permutations(X,N)):
    B=[]
    for j in range(N-1):
        B.append(math.sqrt((i[j][0]-i[j+1][0])**2+(i[j][1]-i[j+1][1])**2))
    A.append(sum(B))
print(mean(A))

Submission status: Accepted

Solution code:
import itertools
import math
n=int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
l=list(range(n))
p=itertools.permutations(l,n)
tot=0
for i in p:
    #print(i)
    for j in range(n-1):
        tot+=math.sqrt((xy[i[j+1]][0]-xy[i[j]][0])**2 + (xy[i[j+1]][1]-xy[i[j]][1])**2)

ans=tot/math.factorial(n)
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math

N = int(input())
xy = [list(map(int,input().split())) for i in range(N)]
d = 0
lis = [x for x in range(N)] # 0からn-1までのリスト
 
permutations_lis = itertools.permutations(lis)# 全ての場合のリストを生成

for one_case in permutations_lis:
    i = 0
    for num in one_case:
        if i == 0:
            a = num
            i += 1
            continue

        x = ((xy[num][0])-(xy[a][0]))**2
        y = ((xy[num][1])-(xy[a][1]))**2
        d += (x + y) **(1/2)

        a = num

print(d / math.factorial(N))

Submission status: Accepted

Solution code:
import itertools
import math

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

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

sum = 0
for v in itertools.permutations(l):
  for i in range(n - 1):
    sum += ((grid[v[i]][0] - grid[v[i + 1]][0]) ** 2 + 
                 (grid[v[i]][1] - grid[v[i + 1]][1]) ** 2) ** (1 / 2)

print(sum / math.factorial(n))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import itertools
import math
n = int(input())
s = [list(map(int, input().split())) for i in range(n)]
a = 0
for j in itertools.permutations(range(n)):
    for k in range(n-1):
        a += ((s[j[k]][0] - s[j[k+1]][0])**2 + (s[j[k]][1] - s[j[k+1]][1])**2)**0.5
print(a/math.factorial(n))

Submission status: Accepted

Solution code:
from copy import deepcopy
import math
import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
x, y = [], []
for _ in range(n):
    xi, yi = list(map(int, input().split()))
    x.append(xi)
    y.append(yi)


def dfs(memo, prex, prey, step, res_):
    global res, counter
    if step == n:
        res += res_
        counter += 1
        return
    for i in range(n):
        if step == 0:
            temp_memo = deepcopy(memo)
            temp_memo[i] = 1
            dfs(temp_memo, x[i], y[i], step + 1, res_)
        else:
            if memo[i]:
                pass
            else:
                temp_memo = deepcopy(memo)
                temp_memo[i] = 1
                dfs(temp_memo, x[i], y[i], step + 1, res_ +
                    (((x[i] - prex) ** 2 + (y[i] - prey) ** 2) ** 0.5))


res = 0
counter = 0
dfs([0 for _ in range(n)], 0, 0, 0, 0)
print(res/counter)

Submission status: Accepted

Solution code:
def main():
    from itertools import permutations
    from math import hypot

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

    def dist(c1, c2):
        return hypot(c1[0] - c2[0], c1[1] - c2[1])

    ans = 0
    for perm in permutations(cities, r=2):
        ans += dist(*perm)
    ans /= N

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import permutations
import math

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

N = int(input())
town = [list(map(int, input().split())) for i in range(N)]
p_town = list(permutations(town, N))
d = [0]*(len(p_town))

#print(p_town)
for i in range(len(p_town)):
  for j in range(N-1):
    dick = p_town[i][j] + p_town[i][j+1]
    d[i] += dist(*dick)
#print(d)

avg = sum(d)/len(d)
print(avg)

Submission status: Accepted

Solution code:
import itertools
import math
n=int(input())
lis=[list(map(int,input().split())) for i in range(n)]
num=[j for j in range(n)]
new=list(itertools.permutations(num))
ans=0
for i in range(len(new)):
    for j in range(n-1):
        a=new[i][j]
        b=new[i][j+1]
        
        ans+=math.sqrt((lis[a][0]-lis[b][0])**2+(lis[a][1]-lis[b][1])**2)
        
print(ans/len(new))

Submission status: Accepted

Solution code:
from itertools import permutations


N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
ans = 0
for i, xys in enumerate(permutations(XY), 1):
    last = xys[0]
    dist = 0
    for xy in xys[1:]:
        dist += ((xy[0] - last[0]) ** 2 + (xy[1] - last[1]) ** 2) ** 0.5
    ans += dist
print(ans / i)

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())
num = [x for x in range(n)]
permutation = itertools.permutations(num)
total = 0
for turn in permutation:
    for j in range(n - 1):
        total += math.sqrt((x[turn[j + 1]] - x[turn[j]]) ** 2 + (y[turn[j+1]] - y[turn[j]]) ** 2)
ans = total / math.factorial(n)
print(ans)

Submission status: Accepted

Solution code:
import itertools


N = int(input())

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

S = 0


route = list(itertools.combinations(P, 2))

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

Submission status: Accepted

Solution code:
import itertools
import math

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


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


for i in itertools.permutations(m, n):
    for j in range(n-1):
        l += f(i[j], i[j+1])

print(l / math.factorial(n))

Submission status: Accepted

Solution code:
import itertools


N = int(input())

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

S = 0


route = list(itertools.combinations(P, 2))

for i in route:
   
   S += ((i[0][0] - i[1][0])**2 + (i[0][1] - i[1][1])**2)**0.5
   
print(S*2/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(i+1,N):
       
       S += ((P[i][0] - P[j][0])**2 + (P[i][1] - P[j][1])**2)**0.5
       
print(S*(2/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:
import math
from itertools import permutations
def inp():return map(int,input().split())
n=int(input())
cd=[[] for _  in range(n+1)]
s=0
for i in range(1,n+1):
    x,y=inp()
    cd[i].append(x)
    cd[i].append(y)

def add(A,n):
    length = 0
    for i in range(n - 1):
        length += math.sqrt((abs(cd[A[i]][0] - cd[A[i + 1]][0])) ** 2 + (abs(cd[A[i]][1] - cd[A[i + 1]][1]))**2)
    return (length)

def num(n):
    p=1
    for i in range(2,n+1):
        p=p*i
    return p


for x in permutations(range(1,n+1),n):
    s=s+add(x,n)
print(s/num(n))

Submission status: Accepted

Solution code:
N, *_XY = open(0).read().split()
N = int(N)
XY = list(zip(*[map(int, iter(_XY))]*2))

import itertools
import numpy as np

routes = list(itertools.permutations(XY, N))

memo = {}
d_list = []

for r in routes:
    d = 0
    for i in range(N-1):
        if (r[i], r[i+1]) in memo.keys():
            d += memo[(r[i], r[i+1])]
        elif (r[i+1], r[i]) in memo.keys():
            d += memo[(r[i+1], r[i])]
        else:
            memo[(r[i], r[i+1])] = np.linalg.norm(np.array(r[i]) - np.array(r[i+1]))
            d += memo[(r[i], r[i+1])]
    d_list.append(d)

print(np.mean(d_list))

Submission status: Accepted

Solution code:
import math

N = int(input())
root = [list(map(int,input().split())) for i in range(N)]
way = []
for i in range(N-1):
    for j in range(i+1,N):
        way.append(math.sqrt((root[i][0]-root[j][0])**2 + (root[i][1]-root[j][1])**2))
ans = sum(way) * (math.factorial(N-1)*2)
print(ans/math.factorial(N))

Submission status: Accepted

Solution code:
#C
import itertools
import math
n = int(input())
adress = []
dstnc = []
for i in range(n):
    adress.append(list(map(int, input().split())))
p = list(itertools.permutations(adress))
for route in p:
    s = 0
    state = route[0]
    for i in range(1,n):
        s += ((state[0] - route[i][0])**2 + (state[1] - route[i][1])**2)**(1/2)
        state = route[i]
    dstnc.append(s)
print(sum(dstnc)/math.factorial(n))

Submission status: Accepted

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

#順列の生成
permi = list(itertools.permutations(range(N)))


sum_kyori = 0
for i in range(math.factorial(N)):
    kyori = 0

    for j in range(1,N):
        
        x_ = (xy[permi[i][j]][0] - xy[permi[i][j-1]][0])**2 
        y_ = (xy[permi[i][j]][1] - xy[permi[i][j-1]][1])**2
        kyori += math.sqrt(x_ + y_)
    sum_kyori += kyori

ans=(float(sum_kyori/math.factorial(N)))
print(ans)

Submission status: Accepted

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

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

print(ans/n)

Submission status: Accepted

Solution code:
import math

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

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

ans = 0    
for i in range(N):
    for j in range(N):
        tmp = math.sqrt((x[i]-x[j])**2+(y[i]-y[j])**2)
        ans += tmp
 
print(ans/N)

Submission status: Accepted

Solution code:
from itertools import permutations
from math import hypot

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

ans = 0
num = 0
for ps in permutations(range(N)):
    dist = 0
    for i in range(N-1):
        dist += hypot(xs[ps[i]]-xs[ps[i+1]], ys[ps[i]]-ys[ps[i+1]])
    ans += dist
    num += 1

print(ans/num)

Submission status: Accepted

Solution code:
import itertools
import math

n = int(input())
X = [[] for _ in range(n)]
Y = [[] for _ in range(n)]

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

Dist = [0 for _ in range(math.factorial(n))]
for i, S in enumerate(itertools.permutations(range(n))):
    for j in range(len(S) - 1):
        Dist[i] += ((X[S[j+1]] - X[S[j]])**2 + (Y[S[j+1]] - Y[S[j]])**2)**(1/2)
print(sum(Dist)/len(Dist))

Submission status: Accepted

Solution code:
import math

N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
R=[]
#print(A)
for i in range(N-1):
    for j in range(i+1,N):
        #print(i,j)
        x=A[i][0]
        y=A[i][1]
        a=A[j][0]
        b=A[j][1]
        tmp=((x-a)**2+(y-b)**2)**0.5
        R.append(tmp)

x=math.factorial(N)
a=(N-1)*x/(len(R))
c=sum(R)
print(c*a/x)

Submission status: Accepted

Solution code:
import itertools
import math
n = int(input())
dis = [[0] * 2 for i in range(n)]
for i in range(n):
    dis[i][0],dis[i][1] = list(map(int,input().split()))
b= [0] * n
for i in range(n):
    b[i] = i + 1
p = list(itertools.combinations(b,2))
ans =0
for i in range(len(p)):
    dist = (dis[p[i][0]-1][0]-dis[p[i][1]-1][0])**2 + (dis[p[i][0]-1][1]-dis[p[i][1]-1][1])**2
    ans += math.sqrt(dist)

print(ans/n * 2)

Submission status: Accepted

Solution code:
# ABC1４５C 

import itertools, math

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

length = 0
length_sum = 0
sum_ = 0

for num, val in enumerate(itertools.permutations(city_list, n)):
    for i in range(len(val) - 1):
        length =  math.sqrt((val[i][0] - val[i + 1][0]) ** 2 +  (val[i][1] - val[i + 1][1]) ** 2)
        length_sum += length
    sum_ += length_sum
    length_sum = 0
    
ans = sum_ / (num + 1)
print(ans)

Submission status: Accepted

Solution code:
import itertools,math

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

d=0
d_all=[]
for i in itertools.permutations(range(N),N):
    for j in range(N-1):
        d+=math.sqrt((X[i[j+1]]-X[i[j]])**2+(Y[i[j+1]]-Y[i[j]])**2)
    d_all.append(d)
    d=0
print(sum(d_all)/math.factorial(N))

Submission status: Accepted

Solution code:
import math

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

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

print(ans/n)

Submission status: Accepted

Solution code:
import itertools
import math

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

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

l=[ i for i in range(N) ]
P=itertools.permutations(l,N)
ans=0
for p in P:
  p=list(p)
  for i in range(N-1):
    ans+=dist[p[i]][p[i+1]]
print(ans/math.factorial(N))

Submission status: Accepted

Solution code:
points = [map(int, raw_input().split(' ')) for _ in range(int(raw_input()))]
def distance(u,v):
	return ((u[1] - v[1]) ** 2 + (u[0] - v[0]) ** 2) ** 0.5
c = [0,0]
def permut(i, points, c):
	if i == len(points):
		tot = 0
		for u,v in zip(points, points[1:]): tot += distance(u,v)
		c[0] +=  tot
		c[1] += 1
		return 
	for j in range(i,len(points)):
		points[i], points[j] = points[j], points[i]
		permut(i+1, points,c)
		points[i], points[j] = points[j], points[i]

permut(0, points,c)

print c[0] / float(c[1])

Submission status: Accepted

Solution code:
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
dist = 0
for x1, y1 in xy:
  for x2, y2 in xy:
    dist += ((x1-x2)**2 + (y1-y2)**2)**(1/2)
print(dist/n)

Submission status: Accepted

Solution code:
n = int(input())
P = [list(map(int, input().split())) for i in range(n)]
s = 0
for i, a in enumerate(P[:-1]):
	for b in P[i+1:]:
		s += ((a[0] - b[0])**2 + (a[1] - b[1])**2)**0.5
print(s / n * 2)

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt, pow, factorial
 
# 座標 a から b の距離を求める
def calc(a, b):
    x1, y1 = a
    x2, y2 = b
    return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2))
 
 
n = int(input())
xy = []
for i in range(n):
    xy.append(list(map(int, input().split())))
 
ans = 0
for order in permutations(range(n)):
    tmp = 0
    for i in range(1, n):
        tmp += calc(xy[order[i]], xy[order[i - 1]])
    ans += tmp
ans /= factorial(n)
 
print(ans)

Submission status: Accepted

Solution code:
import math
import itertools

def main():
    r = [tuple(map(int, input().split())) for _ in range(int(input()))]
    d = 0
    for x in itertools.permutations(r):
        #print("x", x)
        for i in range(len(x)-1):
            d += math.sqrt((x[i][0]-x[i+1][0])**2 + (x[i][1]-x[i+1][1])**2)
    print(d/math.factorial(len(r)))
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

n = int(input())

town = []

ans = 0

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

for i in range(n):
    for s in range(i,n):
        ans += math.sqrt((town[i][0]-town[s][0])**2+(town[i][1]-town[s][1])**2)
        
print(ans*2/n)

Submission status: Accepted

Solution code:
n=int(input())
k = [list(map(int, input().split())) for i in range(n)]
import math
ans=0
p=(n*(n-1))//2
z=math.factorial(n)
q=z*(n-1)
for i in range(n-1):
    for j in range(i+1,n):
        z=math.sqrt((k[i][0]-k[j][0])**2+((k[i][1]-k[j][1])**2))
        ans+=(q/p)*z

z=math.factorial(n)
print(ans/z)

Submission status: Accepted

Solution code:
def dist(p1,p2):
    x1, y1 = p1
    x2, y2 = p2
    return ((x2-x1)**2+(y2-y1)**2)**.5

def combi(m,n):
    a=1
    b=1
    for i in range(n):
        a*=m-i
        b*=(i+1)
    return a//b

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

edge=[]
for i in range(n):
    for j in range(i+1,n):
        edge.append(dist(a[i],a[j]))

c = combi(n,2)
ans = sum(edge)*(combi(c-1,n-2))/(combi(c,n-1))
print(ans)

Submission status: Accepted

Solution code:
from math import sqrt
from itertools import combinations
N = int(input())
points = tuple(tuple(map(int,input().split())) for _ in range(N))
print(sum(sqrt((x1-x2)**2+(y1-y2)**2) for (x1,y1),(x2,y2) in combinations(points,2))*2/N)

Submission status: Accepted

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

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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


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

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

    print(2 * ans / N)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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


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

    dist = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(i + 1, N):
            dist[i][j] = dist[j][i] = distance2(C[i][0], C[i][1], C[j][0], C[j][1])

    ans = 0
    for perm in permutations(range(N)):
        for i in range(N - 1):
            ans += dist[perm[i]][perm[i + 1]]

    print(ans / factorial(N))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def distance(p, q):
    return sum((px - qx) ** 2.0 for px, qx in zip(p, q)) ** 0.5


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

    dist = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(i + 1, N):
            dist[i][j] = dist[j][i] = distance(C[i], C[j])

    ans = 0
    for perm in permutations(range(N)):
        for i in range(N - 1):
            ans += dist[perm[i]][perm[i + 1]]

    print(ans / factorial(N))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import permutations
from itertools import combinations
from math import sqrt
from math import factorial
from collections import defaultdict

N = int(input())

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

length = defaultdict(float)
l_sum = 0
res = 0

for a, b in combinations(range(N),2):
    length[(a, b)] = (sqrt( (points[a][0] - points[b][0])**2 + (points[a][1] - points[b][1])**2 ))

for a in permutations(range(N)):
    for i in range(N-1):
        l_sum += length[(min(a[i], a[i+1]), max(a[i], a[i+1]))]

res = l_sum/factorial(N)

print(res)

Submission status: Accepted

Solution code:
import itertools
import math

n=int(input())
townRoot=list(itertools.permutations([i for i in range(1,n+1)]))
townList=[]
for i in range(n):
    townList.append(tuple([int(i) for i in input().split()]))
sumLenght=0
length=0
for root in townRoot:
    for xy in range(n-1):
        town1=root[xy] -1
        town2=root[xy+1] -1
        length += math.sqrt((townList[town1][0] - townList[town2][0])**2 \
                + (townList[town1][1] - townList[town2][1])**2)
    sumLenght += length
    length = 0
print(sumLenght/len(townRoot))

Submission status: Accepted

Solution code:
import itertools
import math
n=int(input())
empty_list=[]
a=[i for i in range(n)]
permutations_list=[list(b) for b in itertools.permutations(a)]
coordinate_list=[list(map(int,input().split())) for _ in range(n)]
for i in range(math.factorial(n)):
  for j in range(n-1):
    empty_list.append(math.sqrt((coordinate_list[(permutations_list[i][j]-1)][0]-coordinate_list[(permutations_list[i][j+1]-1)][0])**2+(coordinate_list[(permutations_list[i][j]-1)][1]-coordinate_list[(permutations_list[i][j+1]-1)][1])**2))
b=int(math.factorial(n))
c=sum(empty_list)
print(c*(n-1)/((n-1)*b))

Submission status: Accepted

Solution code:
import itertools

n = int(input())
lis = []
keep = [0, 1, 2, 3, 4, 5, 6, 7, 8]
keep = list(itertools.permutations(keep[:n]))
for i in range(n):
    s = list(map(int, input().split()))
    lis.append(s)
ans = 0
re_ans = 0
for j in range(len(keep)):
    for k in range(n - 1):
        ans = ((lis[keep[j][k]][0] - lis[keep[j][k + 1]][0])**2 +
               (lis[keep[j][k]][1] - lis[keep[j][k + 1]][1])**2)**(1 / 2)
        re_ans += ans
print(re_ans / len(keep))

Submission status: Accepted

Solution code:
import itertools

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

nums = [i for i in range(N)] 
numlist = list(itertools.permutations(nums))
L = []
for n in numlist:
  l = 0
  for i in range(N - 1):
    d = (XY[n[i]][0] - XY[n[i + 1]][0]) **2 + (XY[n[i]][1] - XY[n[i + 1]][1]) ** 2
    l += d ** (1/2)
  L.append(l)  
print(sum(L)/len(L))

Submission status: Accepted

Solution code:
import itertools, math

N = int(input())
xy = [map(int, input().split()) for _ in range(N)]
x, y = [list(i) for i in zip(*xy)]

sum = 0

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

for path in pathes:
    prev_x, prev_y = (x[path[0]], y[path[0]])
    for i in path:
        sum += ((x[i]-prev_x)**2 + (y[i]-prev_y)**2)**0.5
        prev_x, prev_y = (x[i], y[i])

print(sum / math.factorial(N))

Submission status: Accepted

Solution code:
from itertools import permutations as pm
n = int(input())
p = [tuple(map(int,input().split())) for _ in range(n)]
def dist(i,j):
    return ((p[i][0]-p[j][0])**2 + (p[i][1]-p[j][1])**2)**(0.5)
ans = 0
m = 0
for l in pm(range(n),n):
    m += 1
    s = 0
    for i in range(n-1):
        s += dist(l[i],l[i+1])
    ans += s
print(ans/m)

Submission status: Accepted

Solution code:
import itertools
import math
n=int(input())
l=[list(map(int,input().split())) for _ in range(n)]
c=itertools.combinations(range(n),2)
lng=0
for a,b in c:
    x1,y1=l[a][0],l[a][1]
    x2,y2=l[b][0],l[b][1]
    lng+=((x2-x1)**2+(y2-y1)**2)**0.5
p=math.factorial(n-1)
print(lng*(p*2)/(p*n))

Submission status: Accepted

Solution code:
import sys
import itertools
import math

input = lambda: sys.stdin.readline().rstrip()


def solve():
    N = int(input())
    X = [0] * N
    Y = [0] * N

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

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

    # print(load)

    ans = 0
    for l in load:
        for i in range(N - 1):
            s = l[i]
            g = l[i + 1]
            ans += math.sqrt(pow(X[s] - X[g], 2) + pow(Y[s] - Y[g], 2))

    ans /= len(load)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

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

Submission status: Accepted

Solution code:
import numpy as np
import math
import itertools

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

def mkdistancelist(N):
    List = list(map(str, [i for i in range(N)]))
    return list(itertools.combinations(List, 2))

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

def caldis(N):
    pairs = mkdistancelist(N)
    placelist = mkmap(N)
    dic = {}
    for pair in pairs:
        label = "".join(pair)
        dic[label] = distance(placelist[int(pair[0])], placelist[int(pair[1])])
    return dic

def mkwayslist(N):
    List = list(map(str, [i for i in range(N)]))
    return list(itertools.permutations(List, N))
            
def mknumdic(ways):
    numdic = {}
    for way in ways:
        for l in range(N-1):    
            tup = sorted((way[l], way[l+1]))
            tup = tup[0] + tup[1]
            if numdic.get(tup) == None:
                numdic[tup] = 1
            else:
                numdic[tup] = numdic[tup] + 1
    return numdic


N = int(input())
dic = caldis(N)
ways = mkwayslist(N)
numdic = mknumdic(ways)

av = np.average(np.array(list(dic.values())))
ans = av * (N-1)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import itertools

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def dist(p, q):
    xdist = p[0] - q[0]
    ydist = p[1] - q[1]
    return (xdist**2 + ydist**2)**0.5


def main():
    N = int(readline())
    ps = [list(map(int, x.split())) for x in readlines()]
    total_dist = 0
    for p, q in itertools.combinations(ps, 2):
        total_dist += dist(p, q)

    ans = total_dist * 2 / N
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

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

spots = [i for i in range(N)]

dist = 0
n = 0
for route in itertools.permutations(spots, N):
    for i in range(N-1):
        start, goal = route[i], route[i+1]
        dist += ((xy[start][0]-xy[goal][0])**2 + (xy[start][1]-xy[goal][1])**2)**0.5
    n += 1

print(dist / n)

Submission status: Accepted

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

def rec(v, length, memo):
    memo[v] = 1

    if -1 not in memo:
        memo[v] = -1
        return length

    length_sum = 0
    for next_v in range(N):
        if memo[next_v] == -1:
            length_sum += rec(next_v, length+((xy[v][0]-xy[next_v][0])**2 + (xy[v][1]-xy[next_v][1])**2) ** 0.5, memo)

    memo[v] = -1
    return length_sum

ans = 0
n = 1
memo = [-1 for i in range(N)]
for i in range(N):
    ans += rec(i, 0, memo)
    n *= i+1

print(ans / n)

Submission status: Accepted

Solution code:
import math
import itertools


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

    dist = 0

    for iter in itertools.permutations(comb):
        for i in range(1, N):
            dist += math.sqrt(pow(xy[iter[i-1]][0]-xy[iter[i]]
                                  [0], 2)+pow(xy[iter[i-1]][1]-xy[iter[i]][1], 2))

    dist = dist/math.factorial(N)
    print(dist)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt

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

root = list(permutations(array, N))

ans = 0
for i in range(len(root)):
    go = list(root[i])
    total = 0
    for j in range(1, N):
        total += sqrt(abs(x[go[j]]-x[go[j-1]])**2 + 
                abs(y[go[j]]-y[go[j-1]])**2)
    ans += total
print(ans/len(root))

Submission status: Accepted

Solution code:
from itertools import permutations
from math import factorial
from math import sqrt

n = int(input())

nf = factorial(n)

xy = []
X = 0
Y = 1

l = [i for i in range(n)]
s = 0

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


for p in permutations(l, n):
    p = list(p)
    for i in range(len(p) - 1):
        s += ((xy[p[i]][X] - xy[p[i+1]][X])**2 + (xy[p[i]][Y] - xy[p[i+1]][Y])**2)**0.5

print(s/nf)