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())
x = []
y = []
ans = []
for _ 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):
        ans_ = pow(((x[i]-x[j])**2 + ((y[i]-y[j])**2)), 0.5)
        ans.append(ans_)
print(sum(ans)/n)

Submission status: Accepted

Solution code:
from itertools import permutations

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

ans=0
cnt=0
for i in permutations(l):
  cnt+=1
  for j in range(len(i)-1):
    ans+=((i[j][0]-i[j+1][0])**2+(i[j][1]-i[j+1][1])**2)**0.5
print(ans/cnt)

Submission status: Accepted

Solution code:
from itertools import permutations

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

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

root = list(permutations(range(0,n)))
dist = 0

for r in root:
    for i in range(1,n):
        dist += ((x[r[i]]-x[r[i-1]])**2 + (y[r[i]]-y[r[i-1]])**2)**0.5

print(dist/len(root))

Submission status: Accepted

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

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

ans *= 2/n

print(ans)

Submission status: Accepted

Solution code:
import itertools


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

def get_dist(town1, town2):
    return ((town1[0]-town2[0]) ** 2 + (town1[1]-town2[1]) ** 2) ** 0.5

ans = 0
for root in itertools.permutations([i for i in range(n)]):
    root_dist = 0
    for i in range(1, len(root)):
        root_dist += get_dist(geo[root[i-1]], geo[root[i]])
    ans += root_dist
print(ans / len(list(itertools.permutations([i for i in range(n)]))))

Submission status: Accepted

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

n = int(input())
a = [x for x in range(1, n+1)]
a = list(permutations(a))
xy = [list(map(int, input().split())) for _ in range(n)]
l = len(a)
result = 0

for ae in a:
  for i in range(n-1):
    tmp = 0
    tmp += (xy[ae[i+1]-1][0] - xy[ae[i]-1][0]) ** 2
    tmp += (xy[ae[i+1]-1][1] - xy[ae[i]-1][1]) ** 2
    result += sqrt(tmp)
print(round(result / l, 10))

Submission status: Accepted

Solution code:
import itertools
import math
n = int(input())
point = []
for _ in range(n):
    x,y = map(int,input().split())
    point.append([x,y])
mati = "1"
root1 = 0
kazu = 0
for i in range(2,n+1):
    i = str(i)
    mati += i
for x in itertools.permutations(mati):
    root2 = 0
    kazu += 1
    for y in range(n-1):
        a = int(x[y])-1
        b = int(x[y+1])-1
        root2 += math.sqrt((point[a][0]-point[b][0])**2 + (point[a][1]-point[b][1])**2)
    root1 += root2
print(root1/kazu)

Submission status: Accepted

Solution code:
n=int(input())
x=[]
y=[]
for i in range(n):
    nx,ny=map(int,input().split())
    x.append(nx)
    y.append(ny)
from itertools import permutations
import math
per=list(permutations(range(n)))
def d(j):
    d=0
    for i in range(n-1):
        dx=abs(x[per[j][i]]-x[per[j][i+1]])
        dy=abs(y[per[j][i]]-y[per[j][i+1]])
        d+=math.sqrt(dx**2+dy**2)
    return d
s=0
for j in range(len(per)):
    s += d(j)
print(s/len(per))

Submission status: Accepted

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

dist_sum = 0
for n, i in enumerate(XY[:-1]):
    for j in XY[n+1:]:
        dist_sum += ((i[0] - j[0])**2 + (i[1] - j[1])**2) ** 0.5
print(dist_sum * 2 / N)

Submission status: Accepted

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

dist_sum = 0
for n, (x_i, y_i) in enumerate(XY[:-1]):
    for (x_j, y_j) in XY[n+1:]:
        dist_sum += ((x_i - x_j)**2 + (y_i - y_j)**2) ** 0.5
print(dist_sum * 2 / N)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy
from math import factorial

def main():
  n = int(input())
  pos = [list(map(int, input().strip().split())) for _ in range(n)]
  pos = numpy.array(pos)
  dists = numpy.zeros((n, n))
  for i in range(n):
    for j in range(i+1, n):
      dists[i, j] = numpy.linalg.norm(pos[i] - pos[j]) 
#   print(dists)
  print(numpy.sum(dists) / n * 2 )

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import itertools
import sys
import math

def distance(p1, p2):
    return math.sqrt(pow(p1[0] - p2[0], 2) + pow(p1[1] - p2[1], 2))

n = int(input())
l = [list(map(int, line.split())) for line in sys.stdin.read().split('\n')[:-1]]
p = itertools.permutations(list(range(n)))
ans = 0
cnt = 0
for arr in p:
    cnt += 1
    for i in range(n-1):
       ans += distance(l[arr[i]], l[arr[i+1]]) 
print(ans/cnt)

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

D = [[0] * N for _ in range(N)]
S = 0
for i in range(N-1):
    for j in range(i+1, N):
        S += math.sqrt((x[i]-x[j])**2 + (y[i]-y[j])**2)


print(S*2/N)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

n = int(input())

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

l = 0
for path in itertools.permutations(xys, n):
    for i in range(n-1):
        nx = path[i+1][0]
        ny = path[i+1][1]
        x  = path[i][0]
        y  = path[i][1]
        l += np.sqrt( (nx-x)**2 + (ny-y)**2 )

for i in range(n):
    l /= (i+1)

print(l)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

n = int(input())

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

l = 0
# cnt = 0.0
for path in itertools.permutations(xys, n):
    # print(path)
    # l = 0.0
    for i in range(n-1):
        nx = path[i+1][0]
        ny = path[i+1][1]
        x  = path[i][0]
        y  = path[i][1]
        l += np.sqrt((nx-x)**2.0 + (ny-y)**2.0)
        # print(l)
    # print(l)
    # cnt += l
    
for i in range(n):
    l /= (i+1)

print(l)

Submission status: Accepted

Solution code:
import math
import itertools
N=int(input())
x=[0]*N
y=[0]*N
for i in range(N):
    a,b=map(int,input().split())
    x[i]=a
    y[i]=b
ans=0
for i in itertools.permutations(range(N)):
    li=list(i)
    for j in range(N-1):
        ans+=math.sqrt((x[li[j]]-x[li[j+1]])**2+(y[li[j]]-y[li[j+1]])**2)
    

print(ans/(math.factorial(N)))

Submission status: Accepted

Solution code:
import itertools

N=int(input())
num=[]
for i in range (N):
    num.append(i)

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

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

l=list(itertools.permutations(num,N))

sum=0
for i in range (len(list(itertools.permutations(num,N)))):
    s=0
    for j in range (N-1):
        s=s+dis(l[i][j],l[i][j+1])
    sum=sum+s

print(sum/len(list(itertools.permutations(num,N))))

Submission status: Accepted

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

import math
Nbikkuri = math.factorial(N)
metchabikkuri = math.factorial(N-1)

for i in range(N-1):
    for j in range(i+1, N):
        dis = ( (loc[i][0] - loc[j][0])**2 + (loc[i][1] - loc[j][1])**2 )**(1/2)
        dis_s += dis*metchabikkuri*2

print(dis_s / Nbikkuri)

Submission status: Accepted

Solution code:
N=int(input())
P=[]
for i in range(0,N):
    P.append(list(map(int,input().split())))
from itertools import permutations
from math import sqrt
total=0
n=0
for i in permutations([j for j in range(0,N)]):
    for j in range(0, N-1):
        total+=sqrt((P[i[j]][0]-P[i[j+1]][0])**2+(P[i[j]][1]-P[i[j+1]][1])**2)
    n+=1
print(total/n)

Submission status: Accepted

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

import itertools

len_list = list(itertools.combinations(xy,2))

length = 0

for i in range(len(len_list)):
    x = len_list[i][0][0] - len_list[i][1][0]
    y = len_list[i][0][1] - len_list[i][1][1]
    length += (x**2+y**2)**0.5
    
print(length/N*2)

Submission status: Accepted

Solution code:
n = int(input())
lis = [list(map(int,input().split())) for _ in range(n)]
s = 0

for i in range(n-1):
    
    for j in range(i+1,n):
        x = (lis[i][0] - lis[j][0])**2
        y = (lis[i][1] - lis[j][1])**2
        s += (x+y)**0.5
print(s*2/n)

Submission status: Accepted

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

def distance(x1,y1,x2,y2):
    return ((x1-x2)**2+(y1-y2)**2)**0.5
def add(n):
    answer = 0
    for i in range(1,n+1):
        answer += i
    return answer


dis_lst = []
for i in range(n-1):
    for j in range(1,n-i):
        x1 = xy_lst[i][0]
        y1 = xy_lst[i][1]
        x2 = xy_lst[i+j][0]
        y2 = xy_lst[i+j][1]
        dis_lst.append(distance(x1,y1,x2,y2))

average = (n-1)/add(n-1)*sum(dis_lst)
print(average)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
XY = [[0]*2]*N
dis = 0
for i in range(N):
  XY[i] = [int(_) for _ in input().split()]
for i in range(N):
  Xi = XY[i][0]
  Yi = XY[i][1]
  for j in range(N):
    Xj = XY[j][0]
    Yj = XY[j][1]
    dis += ((Xi-Xj)**2 + (Yi-Yj)**2)**0.5

print(dis/N)

Submission status: Accepted

Solution code:
import itertools
import math
n = int(input())
positions = []
for i in range(n):
    x, y = map(int, input().split())
    positions.append([x, y])
# print(positions)
ans = 0
for i in itertools.permutations(positions):
    total_distance = 0
    for j in range(1, len(i)):
        x_gap = i[j][0] - i[j - 1][0]
        y_gap = i[j][1] - i[j - 1][1]
        total_distance += math.sqrt(x_gap ** 2 + y_gap ** 2)
    ans += total_distance
ans /= math.factorial(n)
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math
N=int(input())
a=[]
kyori_list=[]
for i in range(N):
    x,y=map(int,input().split())
    a.append((x,y))
for j in itertools.permutations(a):
    k=list(j)
    
    cnt=0
    sum=0
    while cnt<N-1:
        kryoi=0
        kyori=((k[cnt+1][0]-k[cnt][0])**2+(k[cnt+1][1]-k[cnt][1])**2)**(1/2)
        cnt+=1
        
        sum+=kyori
    kyori_list.append(sum)
c=0

for i in kyori_list:
    c+=i
    
    
print(c/math.factorial(N))

Submission status: Accepted

Solution code:
N = int(input())
p = [None] * N

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

ans = 0
for i in range(N):
    for j in range(N):
        d = pow((p[i][0] - p[j][0])**2 + (p[i][1] - p[j][1])**2, 1/2)
        ans += d / N

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
N=int(input())
zahyo=[None]*N
for i in range(N):
    zahyo[i]= list(map(int,input().split()))
lensum=0
for i in range(N):
    j=i+1
    while j<N:
        lensum+=math.sqrt((zahyo[i][0]-zahyo[j][0])**2+(zahyo[i][1]-zahyo[j][1])**2)
        j+=1
print(lensum*2/N)

Submission status: Accepted

Solution code:
n = int(input())
L = [list(map(int, input().split())) for _ in range(n)]
ans = 0
# (edgesの長さの総和)/(edgeの本数)*(1つのpathを構成するedgesの数)
# = (edgesの長さの総和)/ (n*(n-1)) * (n-1)
for x1, y1 in L:
    for x2, y2 in L:
        ans += ((x1 - x2)**2 + (y1 - y2)**2)**.5
print(ans/n)

Submission status: Accepted

Solution code:
import math
from itertools import permutations


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

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

for v in permutations(mati,N):
    for i in range(N-1):
        total += get_distance(v[i+1], v[i])
print(total/math.factorial(N))

Submission status: Accepted

Solution code:
from math import sqrt

n = int(input())
XY = [list(map(int, input().split())) for _ in range(n)]
total = sum(
    sqrt((XY[i][0] - XY[j][0])**2 + (XY[i][1] - XY[j][1])**2)
    for i in range(n)
    for j in range(i + 1, n)
)

print(2 * total / n)

Submission status: Accepted

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

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

ans *= 2 / N

print(ans)

Submission status: Accepted

Solution code:
from math import sqrt, factorial

n = int(input())
XY = [list(map(int, input().split())) for _ in range(n)]
total = sum(
    factorial(n - 1) * sqrt((XY[i][0] - XY[j][0])**2 + (XY[i][1] - XY[j][1])**2)
    for i in range(n)
    for j in range(i + 1, n)
)

print(2 * total / factorial(n))

Submission status: Accepted

Solution code:
from unittest.mock import patch
from math import sqrt, factorial
from itertools import permutations

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

total_sum = 0
for l in permutations(range(N)):
  total_sum += sum(sqrt((XY[l[i+1]][0] - XY[l[i]][0])**2 + (XY[l[i+1]][1]- XY[l[i]][1])**2) for i in range(N-1))
print(total_sum / factorial(N))

Submission status: Accepted

Solution code:
import itertools
import math

distance = lambda p,q: ((p[0]-q[0])**2+(p[1]-q[1])**2)**(0.5)

def solve():
    N = int(input())
    xy = [list(map(int, input().split())) for _ in range(N)]
    distances = [[0 for _ in range(N)] for _ in range(N)]
    for p1,p2 in itertools.combinations(range(N), 2):
        distances[p1][p2] = distance(xy[p1],xy[p2])
        
    ret = 0
    total = math.factorial(N)
    for ps in itertools.permutations(range(N), N):
        s = ps[0]
        for p in ps[1:]:
            s_ = s; p_ = p
            if s > p: s_,p_ = p_,s_
            ret += distances[s_][p_]
            s = p
            
    print(ret / total)
    
solve()

Submission status: Accepted

Solution code:
import itertools
import math

N = int(input())

xy = []

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

d = 0
e = 0
for i in itertools.permutations(list(range(N)), N):
    e += 1
    for j in range(N - 1):
        a = pow(xy[i[j]][0] - xy[i[j+1]][0], 2)
        b = pow(xy[i[j]][1] - xy[i[j+1]][1], 2)
        c = math.sqrt(a+b)
        d += c
print(d/e)

Submission status: Accepted

Solution code:
n=int(input())

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

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

dist=0
for i in range(n):
    for j in range(n):
        dist+=((x[i]-x[j])**2+(y[i]-y[j])**2)**0.5
        
print(dist/n)

Submission status: Accepted

Solution code:
from itertools import combinations
n = int(input())
P = []
for i in range(n):
    xy = list(map(int, input().split()))
    P.append(xy)

#全部の組み合わせの総合距離を求める
L = 0
for v in combinations(range(n), 2):
    V = list(v)
    L += ((P[V[0]][0] - P[V[1]][0])** 2 + (P[V[0]][1] - P[V[1]][1])** 2)** 0.5    

#ある区間が使われるのは2×(n-1)!通り　※例えば(1,2)をひとまとまりとすると順列は(n-1)!とおり(2,1)の順もあるので2倍する
#全部の順列はn!とおり
#よって答えは
print(L * 2 / n)

Submission status: Accepted

Solution code:
from math import sqrt
n = int(input())
town = []
for i in range(n):
    town.append([int(i) for i in input().split()])
distance = 0
for i in range(n):
    for j in range(i + 1, n):
        distance += sqrt((town[i][0] - town[j][0])**2 + (town[i][1] - town[j][1])**2)
distance *= (2 / n)
print(distance)

Submission status: Accepted

Solution code:
import itertools
import math
def dis(X,Y):
    return ((X[0]-Y[0])**2+(X[1]-Y[1])**2)**.5
def main():
    n=int(input())
    L=[list(map(int,input().split())) for _ in range(n)]
    S=itertools.permutations([i for i in range(1,n+1)])
    ans=0
    for s in S:
        for i in range(n-1):
            a = s[i] - 1
            b = s[i+1] - 1
            ans += dis(L[a],L[b])
    ans /= math.factorial(n)
    print(ans)
main()

Submission status: Accepted

Solution code:
from math import sqrt

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

    s=0
    for i in range(0,N):
        for j in range(0,N):
            s=s+sqrt((x[i]-x[j])**2+(y[i]-y[j])**2)
    s=s/N
    print(s)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
xy=[[0]*2]*n #二次配列
for i in range(n):
	xy[i] = [int(kyori) for kyori in input().split()]
	
dis = 0 #各町間の距離の総和
for i in range(n):
	xi = xy[i][0]
	yi = xy[i][1]
	for j in range(i+1,n):
		xj = xy[j][0]
		yj = xy[j][1]
		dis += ((xi-xj)**2 + (yi-yj)**2)**0.5
		
print(dis*2/n)

Submission status: Accepted

Solution code:
import math

N = int(input())
P = [list(map(int, input().split())) for _ in range(N)]
dis = 0
c = 0

for i in range(N):
    xi = P[i][0]
    yi = P[i][1]
    for ii in range(i + 1, N):
        xj = P[ii][0]
        yj = P[ii][1]
        dis += ((xi - xj)**2 + (yi - yj)**2)**0.5
        c += 1
print(dis / c * (N - 1))

Submission status: Accepted

Solution code:
N = int(input())
P = [list(map(int, input().split())) for _ in range(N)]
ans = 0
c = 0

def dfs(i, dis, passed):
    if len(passed) == N:
        global c, ans
        c += 1
        ans += dis
        return
    x = P[i][0]
    y = P[i][1]
    for ii in range(N):
        if P[ii] in passed:
            continue
        xx = P[ii][0]
        yy = P[ii][1]
        passed.append([xx, yy])
        dfs(ii, dis + ((x - xx)**2 + (y - yy)**2)**0.5, passed)
        passed.pop(-1)

for i in range(N):
    dfs(i, 0, [P[i]])
print(ans / c)

Submission status: Accepted

Solution code:
def main():
    from itertools import permutations
    import math
    import numpy as np
    tot = 0

    N = int(input())
    locs = np.array([
        [int(x) for x in input().split()]
        for _ in range(N)
    ], dtype=float)

    for order in permutations(range(N)):
        order = list(order)
        loc0 = locs[order[:-1]]
        loc1 = locs[order[1:]]
        delta = loc1 - loc0
        tot += np.sum(np.linalg.norm(delta, axis=1))
    print(tot/math.factorial(N))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
ans=0
XY=[]
for i in range(N):
    X,Y = list(map(int,input().split()))
    for xy in XY:
        ans += ((xy[0]-X)**2+(xy[1]-Y)**2)**0.5
    XY.append((X,Y))
print(ans*2/N)

Submission status: Accepted

Solution code:
N = int(input())

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

distance = []
for i in range(N):
    for j in range(i+1, N):
        x1, y1 = coordinates[i]
        x2, y2 = coordinates[j]
        d = math.sqrt((x1-x2)**2+(y1-y2)**2)
        distance.append(d)
        
        
each_pattern = 1
for i in range(1, N):
    each_pattern *= i
each_pattern *= 2

total_distance = 0
for d in distance:
    total_distance += d*each_pattern
    
pass_pattern = 1
for i in range(1, N+1):
    pass_pattern *= i
    
print(total_distance / pass_pattern)

Submission status: Accepted

Solution code:
import math
import itertools

n=int(input())
f=math.factorial(n)
p=[]
for _ in range(n):
  x,y=map(int,input().split())
  p.append([x,y])
  
def distance(x,y):
  return(((x[0]-y[0])**2+(x[1]-y[1])**2)**.5 )

ans=0
for path in list(itertools.permutations(range(n))):
  arr=[p[i] for i in path]
  ans+=sum([distance(x,y)/f for x,y in zip(arr[:-1],arr[1:])])
print(ans)

Submission status: Accepted

Solution code:
import math

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

def distance(a,b,d):
    global D
    if a.count(True) == 0:
        D += d
        return
    for i in range(N):
        if a[i] == True:
            a[i] = False
            dd = math.sqrt((x[i] - x[b]) ** 2 + (y[i] - y[b]) ** 2)
            d += dd
            distance(a,i,d)
            a[i] = True
            d -= dd

for i in range(N):
    z[i] = False
    d = 0
    distance(z,i,d)
    z[i] = True

print (D / math.factorial(N))

Submission status: Accepted

Solution code:
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)

D = [[0 for _ in range(N)] for _ in range(N)]

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)


res = 0
for t in itertools.permutations([i for i in range(N)]):
    for j in range(1, N):
        res += D[t[j]][t[j - 1]]
print(res / math.factorial(N))

Submission status: Accepted

Solution code:
from itertools import permutations

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

al = list(permutations(range(N)))
ttmp = []
for a in al:
    tmp = 0
    h = a[0]
    for i in a[1:]:
        tmp += ((x[h] - x[i]) ** 2 + (y[h] - y[i]) ** 2) ** 0.5
        h = i
    ttmp.append(tmp)
print(sum(ttmp) / len(al))

Submission status: Accepted

Solution code:
import math

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

sum = 0
num = 0

for i in range(n - 1):
    for j in range(i + 1, n):
        sum += math.sqrt((d[i][0] - d[j][0]) ** 2 + (d[i][1] - d[j][1]) ** 2)
        num += 1

print(sum / num * (n - 1))

Submission status: Accepted

Solution code:
import itertools
import math

def main():
    N = int(input())

    xys = [[int(y) for y in input().split()] for _ in range(N)]

    routes = itertools.permutations(xys, len(xys))

    sumup = 0
    count = 0 # cuz len(routes) doesn't work :(
    for route in routes:
        count += 1
        for i in range(1, N):
            xy_0 = route[i - 1]
            xy_1 = route[i]
            sumup += math.sqrt((xy_0[0] - xy_1[0]) ** 2 + (xy_0[1] - xy_1[1]) ** 2)

    print(sumup / count)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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


cs = list(itertools.combinations(points,2))
ans = 0
for a,b in cs:
    c = (a[0]-b[0]) ** 2 + (a[1]-b[1]) ** 2
    ans += math.sqrt(c)

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

Submission status: Accepted

Solution code:
import sys,math
import itertools

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N = II()
	pos = LLI(N)
	dist = [[0 for _ in range(N)] for _ in range(N)]
	total = 0
	for i in range(N):
		for j in range(i+1,N):
			dist[i][j] = math.sqrt((pos[i][0]-pos[j][0])**2 + (pos[i][1]-pos[j][1])**2)
			dist[j][i] = dist[i][j]
		total += sum(dist[i])
	print(total/N)

main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

city = [LIST() for _ in range(N)]

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

a = list(permutations(per))

sums = 0
for i in a:
	path = 0
	for j in range(N - 1):
		path += sqrt((city[i[j]][0] - city[i[j+1]][0])**2 + (city[i[j]][1] - city[i[j+1]][1])**2 )
	sums += path

print(sums/len(list(a)))

Submission status: Accepted

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

import itertools
import math
temp=[i for i in range(n)]
perm=list(itertools.permutations(temp))

sm=0
count=0
for route in perm:
    count+=1
    temp_dis=0
    route_list=list(route)
    for i in range(1,n):
        j=route_list[i]
        k=route_list[i-1]
        temp_dis+=math.sqrt((distance[j][0]-distance[k][0])**2+(distance[j][1]-distance[k][1])**2)
    sm+=temp_dis
ans=sm/count
print('{:.9f}'.format(ans))

Submission status: Accepted

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

import itertools,math

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

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

total = 0

for pt in ptr:
  for i in range(len(p)-1):
    total += dist(p[pt[i]] ,p[pt[i+1]])  
print(total/len(ptr))

Submission status: Accepted

Solution code:
import itertools
N = int(input())
root = []
for i in range(N):
    num= [int(i) for i in input().split()]
    root.append(num)
#ここまで入力

n_list = list(itertools.permutations(root))
dist1 = []
for i in n_list:
    dist = 0
    for j in range(1,N):
        dist = dist + ((i[j][0]-i[j-1][0])**2+(i[j][1]-i[j-1][1])**2)**(1/2)
    dist1.append(dist)
print(sum(dist1)/len(dist1))

Submission status: Accepted

Solution code:
import math
N=int(input())
A = []
B = []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
cnt = 0
for i in range(N-1):
    for j in range(i+1,N,1):
        cnt +=math.sqrt((A[i]-A[j])**2+(B[i]-B[j])**2)
print(cnt*2/N)

Submission status: Accepted

Solution code:
import math
from itertools import permutations


class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def distance_to(self, p):
        dx = p.x - self.x
        dy = p.y - self.y
        return math.sqrt(dx * dx + dy * dy)


def route_distance(ps):
    if len(ps) < 2:
        return 0
    else:
        return ps[0].distance_to(ps[1]) + route_distance(ps[1:])


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

    sum_routes = sum(route_distance(ps) for ps in permutations(ps, N))
    print(sum_routes / math.factorial(N))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
xy = []
for _ in range(n):
	xy.append([int(x) for x in input().split()])
dis = 0
for x1, y1 in xy:
	for x2, y2 in xy:
		#print(x1,y1,x2,y2)
		dis += ((x1 - x2)**2 + (y1 - y2)**2)**0.5
print(dis/n)

Submission status: Accepted

Solution code:
import itertools
n = int(input())
point = []
for i in range(n):
  a,b = map(float,input().split())
  point.append((a,b))
ans = 0.0
div = 0
for pm in itertools.permutations(point):
  div += 1
  for j in range(n-1):
    ans += ((pm[j][0]-pm[j+1][0])**2 + (pm[j][1]-pm[j+1][1])**2) ** 0.5
print(ans / div)

Submission status: Accepted

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

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

N = int(readline())
XY = np.array(read().split(), np.int64)

X = XY[::2]
Y = XY[1::2]

dx = X[None, :] - X[:, None]
dy = Y[None, :] - Y[:, None]

dist_mat = (dx * dx + dy * dy) ** .5
ans = dist_mat.sum() / N

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
sys.setrecursionlimit(10 ** 7)

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

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

        ci = CITY[i]
        cj = CITY[j]
        d = math.sqrt((ci[0] - cj[0]) ** 2 + (ci[1] - cj[1]) ** 2)
        l += math.factorial(N - 1) * d

print(l / math.factorial(N))

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt

N = int(input())
l = [tuple(map(int, input().split())) for _ in range(N)]
ans = 0
n = 0

for i in permutations(l):
    for j in range(N-1):
        x1, y1 = i[j]
        x2, y2 = i[j+1]
        ans += sqrt((x1-x2)**2+(y1-y2)**2)
    n += 1

print(ans/n)

Submission status: Accepted

Solution code:
import numpy as np

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

res = 0
for i in range(len(m)):
    for j in range(i+1, len(m)):
        res += np.sqrt((m[i][0] - m[j][0]) ** 2 + (m[i][1] - m[j][1]) ** 2)
        
print(res * 2 / N)

Submission status: Accepted

Solution code:
import math
import itertools

n = int(input())
xy = [ list(map(int, input().split())) for _ in range(n) ]
p = itertools.permutations(xy, n)
c = 0
for i in p:
  for j in range(n-1):
    c += ( (i[j][0]-i[j+1][0])**2 + (i[j][1]-i[j+1][1])**2 )**0.5
    
l = math.factorial(n)
print(c/l)

Submission status: Accepted

Solution code:
n = int(input())
list = []
for i in range(n):
  a = [int(j) for j in input().split()]
  list.append(a)
  
root = []
for i in range(n):
  for j in range(i+1, n, 1):
    a = list[i]
    b = list[j]
    r =  ((a[0]-b[0])**2 + (a[1]-b[1])**2)**(1/2)
    root.append(r)
    
print((sum(root)*(n-1))/((n*(n-1))/2))