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 sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    C=[None]*n
    for i in range(n):
        x,y=map(int,input().split())
        C[i]=x+y*1j

    s=sum(abs(C[i]-C[j]) for i in range(n) for j in range(n))
    print(s/n)
resolve()

Submission status: Accepted

Solution code:
N = int(input())
lis = [list(map(int, input().split())) for i in range(N)]
# 二点間の距離の計算
import math
def dist(x1,y1,x2,y2):
  x = (x1-x2)**2 + (y1-y2)**2
  return math.sqrt(x)

# 並び順のパターン
import itertools
rt_list = list(itertools.permutations(range(N)))

d = 0
for rts in rt_list:
  tmp_d = 0 #このルートでの総距離
  for rt in range(len(rts) - 1):
    tmp_d += dist(lis[rts[rt]][0],lis[rts[rt]][1], lis[rts[rt+1]][0],lis[rts[rt+1]][1])
  d += tmp_d
print(d/len(rt_list))

Submission status: Accepted

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

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

path = []
for l in itertools.permutations(xy):
    t = 0
    for i in range(N-1):
        t += math.sqrt((l[i][0] - l[i+1][0]) ** 2 + (l[i][1] - l[i+1][1]) ** 2)
    path.append(t)

print(sum(path)/len(path))

Submission status: Accepted

Solution code:
import math
from itertools import permutations
N = int(input())
TOWNS = [tuple(map(int, input().split())) for _ in range(N)]

cands = [p for p in permutations([i for i in range(0, N)], N)]
s = 0
for cand in cands:
    for i in range(N-1):
        start = TOWNS[cand[i]]
        dist = TOWNS[cand[i+1]]
        s += math.sqrt((start[0] - dist[0])**2 + (start[1] - dist[1])**2)

print(s / math.factorial(N))

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())

address_list = []
for i in range(N):
    x, y = map(int, input().split())
    address_list.append([x, y])
    
distance_list = np.zeros([N, N])
for l in range(N):
    for m in range(N):
        x_1 = address_list[l][0]
        y_1 = address_list[l][1]
        x_2 = address_list[m][0]
        y_2 = address_list[m][1]
                              
        distance_list[l][m] = np.sqrt((x_1 - x_2) ** 2 + (y_1 - y_2) ** 2)
        
ans = distance_list.sum() / N
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=[]
s=0
f=1
for i in range(2,n+1):
    f*=i
for _ in range(n):
    l.append(list(map(int,input().split())))
for i in range(n-1):
    for j in range(i+1,n):
        s+=((l[i][0]-l[j][0])**2+(l[i][1]-l[j][1])**2)**.5
s=s*f/n*2
s=s/f
print(s)

Submission status: Accepted

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

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

def factorial(n):
    if n==1:
        return 1
    else:
        return n*factorial(n-1)

total = 0
for i in range(N):
    for j in range(i+1, N):
        total += dist(x[i], x[j], y[i], y[j])

line_num = N*(N-1)/2 #線分の数
path_num = (N-1)*factorial(N)/line_num #ある線分が経路に含まれている数=1つの経路の線分の数×全経路数÷一意の線分の数

print(path_num*total/factorial(N))

Submission status: Accepted

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

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

def factorial(n):
    if n==1:
        return 1
    else:
        return n*factorial(n-1)

total = 0
for i in range(N):
    for j in range(i+1, N):
        total += dist(x[i], x[j], y[i], y[j])

line_num = N*(N-1)/2
path_num = (N-1)*factorial(N)/line_num

print(path_num*total/factorial(N))

Submission status: Accepted

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

whole_dist=0
for i in range(N):
    for j in range(N):
        if (i!=j):
            whole_dist += ((x[i]-x[j])**2+(y[i]-y[j])**2)**(1/2)

print(whole_dist/N)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import permutations

import math

def main():
    N = int(input())
    xs = np.zeros(N)
    ys = np.zeros(N)
    for i in range(N):
        x, y = list(map(int, input().split()))
        xs[i] = x
        ys[i] = y
    dist_mat = np.sqrt((xs[:, np.newaxis] - xs[np.newaxis, :])**2
                       + (ys[:, np.newaxis] - ys[np.newaxis, :])**2)
    # print(dist_mat)
    assert dist_mat.shape == (N, N)

    perm = permutations(list(range(N)))

    avg_path_length = 0
    n = 1
    for seq in perm:
        path_length = np.sum([dist_mat[seq[i], seq[i+1]] for i in range(N-1)])
        avg_path_length = avg_path_length / n * (n-1) + path_length / n
        n+= 1
    assert n == math.factorial(N)+1

    print(avg_path_length)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

total = 0

for i in range(N - 1):
    xi = p[i][0]
    yi = p[i][1]
    for j in range(i + 1, N):
        xj = p[j][0]
        yj = p[j][1]
        total += ((xi - xj) ** 2 + (yi - yj) ** 2) ** 0.5

ans = total * 2 / N

print(ans)

Submission status: Accepted

Solution code:
def factorial(num):
    res = 1
    for i in range(num):
        res *= i + 1
    return res


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

total = 0

for i in range(N - 1):
    xi = p[i][0]
    yi = p[i][1]
    for j in range(i + 1, N):
        xj = p[j][0]
        yj = p[j][1]
        distance = ((xi - xj) ** 2 + (yi - yj) ** 2) ** 0.5
        total += distance * factorial(N - 1) * 2

ans = total / factorial(N)

print(ans)

Submission status: Accepted

Solution code:
import itertools
import math

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

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

s = 0
for i in itertools.permutations(XY):
    for j in range(N-1):
        XY0 = i[j]
        XY1 = i[j+1]
        s += dist(XY0[0],XY0[1],XY1[0],XY1[1])

print(s / math.factorial(N))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def fct(n):
    if n == 1:
        return 1
    return n * fct(n-1)

def main():
    N = I()
    pos = []
    ans = 0
    G = [[0 for __ in range(N)] for _ in range(N)]
    for _ in range(N):
        x, y = LF()
        pos.append((x, y))
    for i in range(N):
        x = pos[i][0]
        y = pos[i][1]
        for j in range(N):
            jx = pos[j][0]
            jy = pos[j][1]
            dist = math.sqrt((x - jx)**2 + (y - jy)**2)
            ans += dist * fct(N-1) 
    print(ans / fct(N))
main()

Submission status: Accepted

Solution code:
from statistics import mean
import itertools
import math

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

pos_comb = itertools.combinations(pos,2)
dis_list = []
for i in pos_comb:
    dis_list.append(math.sqrt((i[0][0]-i[1][0])**2+(i[0][1]-i[1][1])**2))

print(mean(dis_list)*(float(n)-1.0))

Submission status: Accepted

Solution code:
from itertools import permutations as pm
n = int(input())
x = [[int(i) for i in input().split()] for i in range(n)]
y,ans = [i for i in range(n)],0
for i in pm(y):
    for j in range(n-1): ans+=((x[i[j]][0]-x[i[j+1]][0])**2+(x[i[j]][1]-x[i[j+1]][1])**2)**0.5
num = 1
for i in range(n): num*=(i+1)
print(ans/num)

Submission status: Accepted

Solution code:
import math
n = int(input())
xy = [tuple(map(int, input().split())) for _ in range(n)]
dists = []
for i in range(n):
  for j in range(i+1, n):
    dx = xy[i][0] - xy[j][0]
    dy = xy[i][1] - xy[j][1]
    dists.append(math.sqrt(dx * dx + dy * dy))
print(2 * sum(dists) / n)

Submission status: Accepted

Solution code:
import math
import itertools
N = int(input())
list = []
for i in range(N):
    a = input().split()
    x = int(a[0])
    y = int(a[1])
    list.append([x, y])
length = 0
count = 0
for v in itertools.permutations(list, len(list)):
    for i in range(len(list)-1):
        tmp = ((v[i][0]-v[i+1][0])*(v[i][0]-v[i+1][0]) + (v[i][1]-v[i+1][1])*(v[i][1]-v[i+1][1]))
        length += math.sqrt(tmp)
    count += 1
print(length/count)

Submission status: Accepted

Solution code:
import math
n = int(input())
p = []
l = []
for _ in range(n):
    x, y = map(int, input().split())
    for i in range(len(p)):
        l.append(math.sqrt((abs(x - p[i][0]) ** 2) + (abs(y - p[i][1]) ** 2)))
    p.append((x, y))
print("{:.10f}".format(sum(l) * (len(p) - 1) / len(l)))

Submission status: Accepted

Solution code:
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
total_distance = 0
for i in range(n):
    for j in range(i+1,n):
        total_distance += ((xy[i][0] - xy[j][0])**2 + (xy[i][1] - xy[j][1])**2)**0.5
print(total_distance*2/n)

Submission status: Accepted

Solution code:
n = int(input())
x=[]
y=[]
for i in range(n):
        x0,y0=list(map(int, input().split()))
        x.append(x0)
        y.append(y0)

import itertools
import math
a=[i for i in range(n)]
com=[]
for v in itertools.permutations(a):
    com.append(v)
sum = 0
for v in com:
  #print("{}:".format(v))
  for i in range(n-1):
    #print(v[i],end="")
    sum+=math.sqrt( (x[ v[i+1] ]-x[ v[i] ])**2+ (y[ v[i+1] ]-y[ v[i] ])**2 )

print(sum/len(com))

Submission status: Accepted

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

xys = [[] for i in range(n)]

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


m = math.factorial(n)
c = [i for i in range(n)]
cs = itertools.permutations(c)

s = 0
for d in cs:
    for j in range(len(d)-1):
        x = (xys[d[j]][0] - xys[d[j+1]][0]) ** 2 + (xys[d[j]][1] - xys[d[j+1]][1]) ** 2
        s += x ** (0.5)

print(s/m)

Submission status: Accepted

Solution code:
import math
import itertools

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

def average(a):
    return (sum(a) / len(a))

N = int(input())
S = [list(map(int, input().split())) for i in range(N)]
l = list(itertools.permutations([i for i in range(N)]))

dist_list = []

for i in l:
    dist = 0
    for j in range(N - 1):
        dist += distance(S[i[j]], S[i[j+1]])
    dist_list.append(dist)

# print(dist_list)
print(average(dist_list))

Submission status: Accepted

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

def dist(A, B):
    return sqrt((A[0] - B[0])**2 + (A[1] - B[1])**2)

tot = 0
for combo in combinations(matrix, 2):
    tot += dist(*combo)

print(tot*2/N)

Submission status: Accepted

Solution code:
import itertools
import math

def kaijo(n):
    if n == 1:
        return 1
    return kaijo(n-1) * n

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

#階乗
ptrs = list(itertools.permutations(seq)) #組み合わせ列挙 5!

ans = 0
for ptr in ptrs:
    for i in range(N-1):
        ans += math.sqrt((L[ptr[i+1]][0] - L[ptr[i]][0]) ** 2 + (L[ptr[i+1]][1] - L[ptr[i]][1]) ** 2)

print(ans/kaijo(N))

Submission status: Accepted

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

def calc_dist(l1,l2):
  return sqrt( (l1[0]-l2[0])**2 + (l1[1]-l2[1])**2 )

result = 0
for v in combinations(xy,2):
  result += calc_dist(*v)
print(result*2/N)

Submission status: Accepted

Solution code:
from itertools import combinations
dist = lambda p1, p2: ((p2[0] - p1[0]) ** 2 + (p2[1] - p1[1]) ** 2) ** (1 / 2)

N = int(input())
P = (tuple(map(int, input().split())) for _ in range(N))

distances = (dist(*combination) for combination in combinations(P, 2))
total_distance = tuple(sum(distance) for distance in combinations(distances, N - 1))
print(sum(total_distance) / len(total_distance))

Submission status: Accepted

Solution code:
N = int(input())
a = [0] * N
b = [0] * N

Ans = 0

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

for i in range(N):
    for k in range(1, N-i):
        Ans += ((a[i]-a[i+k])**2 +(b[i]-b[i+k])**2)**0.5 

print(Ans*2/N)

Submission status: Accepted

Solution code:
#ABC-145-C
import itertools
N = int(input())
xy_list = []
for _ in range(N):
    x, y = map(int, input().split())
    xy_list.append((x, y))

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

#任意の二つの街の距離を先に計算してdistance_listに格納しておく。
distance_list = [[0] * N for i in range(N)]

for i in range(N):
    for j in range(N):
        if i ==j:
            continue
        distance_list[i][j] = get_distance(xy_list[i][0], xy_list[i][1], xy_list[j][0], xy_list[j][1])

machi_list = [i for i in range(N)]
travel_list = list(itertools.permutations(machi_list))

summed_distance = 0
for travel in travel_list:
    for i in range(N-1):
        summed_distance += distance_list[travel[i]][travel[i+1]]
        
print(summed_distance/len(travel_list))

Submission status: Accepted

Solution code:
N = int(input())
xy = [[0 for i in range(2)] for j in range(N)]
for n in range(N):
    xy[n][0],xy[n][1] = map(int, input().split())
route = N*(N-1)
Length = 0
for i in range(N-1):
    for j in range(i+1,N):
        Length = Length + ((xy[i][0]-xy[j][0])**2+(xy[i][1]-xy[j][1])**2)**(1/2)
Length_ave = Length*((N-2)*2+2)/route
print(Length_ave)

Submission status: Accepted

Solution code:
import itertools
import math
N=int(input())
T=[None]*N
for i in range(N):
    T[i] = list(map(int,input().split()))

seq=[i for i in range(N)]
kumi=list(itertools.permutations(seq))
L_sum=0
for i in range(len(kumi)):
    for j in range(N-1):
        L_sum+=math.sqrt((T[kumi[i][j]-1][0]-T[kumi[i][j+1]-1][0])**2+(T[kumi[i][j]-1][1]-T[kumi[i][j+1]-1][1])**2)
        #print(kumi[i][j],kumi[i][j+1])
        #,T[kumi[i][j+1]-1][0],T[kumi[i][j]-1][1],T[kumi[i][j+1]-1][1])
num=1
for i in range(1,N+1):
    num*=i
#print(L_sum)
print(L_sum/num)

Submission status: Accepted

Solution code:
# coding: utf-8
from itertools import permutations
from math import sqrt

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

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

ans = 0
for i in permutations(range(N)):
    for j in range(len(i)-1):
        ans += calc(X[i[j]], Y[i[j]], X[i[j+1]], Y[i[j+1]])

print(ans / len(list(permutations(range(N)))))

Submission status: Accepted

Solution code:
import math
n = int(input())
r = [(input().split()) for _ in range(n)]
r = [(float(i),float(j)) for (i,j) in r]
total = 0
for i, (x,y) in enumerate(r):
    for a,b in r[i+1:]:
        length = math.sqrt((x-a)**2 + (y-b)**2)
        total += length
print(2*total/n)

Submission status: Accepted

Solution code:
import itertools,math
N = int(input())
x = [] 
y = []
for _ in range(N):
    a,b = map(int,input().split())
    x.append(a)
    y.append(b)
summation = 0

def dist(i,j):
    return math.sqrt((x[i] - x[j])**2 + (y[i]-y[j])**2)
permutations = list(itertools.permutations(range(N)))
for perm in permutations:
    subSum = 0
    for i in range(N-1):
        subSum += dist(perm[i], perm[i+1])
    summation += subSum

answer = summation / len(permutations)
print(answer)

Submission status: Accepted

Solution code:
def kaijo(n):
    if(n==1):
        return 1
    else:
        return n*kaijo(n-1)

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

sum_dist = 0

for i in range(N):
    for j in range(N):
        if(i==j):continue
        sum_dist += ((pt[i][0]-pt[j][0])**2+(pt[i][1]-pt[j][1])**2)**0.5*kaijo(N-1)


print(sum_dist/kaijo(N))

Submission status: Accepted

Solution code:
from math import sqrt
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
result=0
nums=[x for x in range(n)]
for i in nums:
  for j in nums:
    if(i!=j):
      result += sqrt((l[i][0] - l[j][0]) * (l[i][0] - l[j][0]) + (l[i][1] - l[j][1]) * (l[i][1] - l[j][1]))
print(result/n)

Submission status: Accepted

Solution code:
import itertools
import math

def dist(s, g):
    sx, sy = s
    ex, ey = g

    return math.sqrt((ex - sx)**2 + (ey - sy)**2)

# input
n = int(input())
points = [ [int(x) for x in input().split()] for _ in range(n) ]

# calculate roots
roots = set(itertools.permutations(range(n)))

distance = [0] * len(roots)
idn = 0
for root in roots:
    for i in range(len(root) - 1):
        tmp_dist = dist(points[root[i]], points[root[i + 1]])
        distance[idn] += tmp_dist
    
    idn += 1

print(sum(distance) / len(distance))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
N=int(input())
Z=[list(map(int, input().split())) for i in range(N)]
A=[[0 for i in range(N)] for j in range(N)]
c=0
def R(a, b):
    return ((Z[a-1][0]-Z[b-1][0])**2 + (Z[a-1][1]-Z[b-1][1])**2)**(1/2)
for i in range(N):
    for j in range(N):
        A[i][j] = R(i+1, j+1)
multi=math.factorial(N-1)*2
for i in range(N):
    for j in range(i):
        c+=A[i][j]
print(2*c/N)

Submission status: Accepted

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

from itertools import permutations
from math import factorial

res = 0
for p in permutations(range(N)):
    for i, j in zip(p, p[1:]):
        x0, y0 = positions[i]
        x1, y1 = positions[j]
        res += ((x1-x0)**2 + (y1-y0)**2)**0.5
print(res/factorial(N))

Submission status: Accepted

Solution code:
import math
import itertools
N=int(input())
s = [list(map(int, input().split())) for _ in range(N)]
x=[]
y=[]
for i in s:
    x.append(i[0])
    y.append(i[1])

r_sum=[]
for i in range(N):
    r_=[]
    for j in range(N):
        r=0
        r=math.sqrt((x[i]-x[j])**2 + (y[i]-y[j])**2)
        r_.append(r)
    r_sum.append(r_)
#print('---')
#print(r_sum)

r_1 = list(itertools.permutations(range(N)))
r_1_cnt = len(r_1)
#print('---')
#print(r_1)

result=0
for i in r_1:
    for j in range(N-1):
        result+=r_sum[i[j]][i[j+1]]
print(result/r_1_cnt)

Submission status: Accepted

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


def distance(R):
	x = []
	y = []
	for i in range(N):
		x.append(int(R[i][0]))
		y.append(int(R[i][1]))
	d = 0
	for i in range(N-1):
		d += math.sqrt((x[i]-x[i+1])**2 + (y[i]-y[i+1])**2)
	return d


		
sum = 0
count = 0
for route in itertools.permutations(xy):
	sum += distance(route)
	distance(route)
	count += 1

print(sum/count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline

from math import sqrt
n = int(input())
d = [list(map(int,input().split())) for i in range(n)]

#町iと町jの距離を計算
distance_nest_list = []
for i in d:
    distance_list = []
    for j in d:
        distance_list.append(sqrt((i[0] - j[0])**2 + (i[1] - j[1])**2))
    distance_nest_list.append(distance_list)

#全経路列挙
from itertools import permutations
path_list = list(permutations(range(n),n))
path_cnt = len(path_list)

ans = 0
for path in path_list:
    for i in range(n-1):
        ans += distance_nest_list[path[i]][path[i+1]]
print(ans/path_cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline

from math import sqrt
n = int(input())
d = [list(map(int,input().split())) for i in range(n)]

#町iと町jの距離を計算
distance_nest_list = []
for i in d:
    distance_list = []
    for j in d:
        distance_list.append(sqrt((i[0] - j[0])**2 + (i[1] - j[1])**2))
    distance_nest_list.append(distance_list)

distance_nest_list_sum_witho_ii = 0
for i,v in enumerate(distance_nest_list):
    for i2,v2 in enumerate(v):
        if i!=i2:
            distance_nest_list_sum_witho_ii+=v2

ans = distance_nest_list_sum_witho_ii/n
print(ans)

Submission status: Accepted

Solution code:
from itertools import product


def solve(string):
    n, *xy = map(int, string.split())
    *xy, = zip(*[iter(xy)] * 2)
    return str(
        sum(((xy[i][0] - xy[j][0])**2 + (xy[i][1] - xy[j][1])**2)**0.5
            for i, j in product(range(n), repeat=2)) / n)


if __name__ == '__main__':
    n = int(input())
    print(solve('{}\n'.format(n) + '\n'.join([input() for _ in range(n)])))

Submission status: Accepted

Solution code:
from itertools import permutations
from functools import reduce
from operator import mul


def solve(string):
    n, *xy = map(int, string.split())
    *xy, = zip(*[iter(xy)] * 2)
    return str(
        sum(
            sum(((xy[p0][0] - xy[p1][0])**2 + (xy[p0][1] - xy[p1][1])**2)**0.5
                for p0, p1 in zip(list(i),
                                  list(i)[1:]))
            for i in permutations(range(n), n)) / reduce(mul, range(1, n + 1)))


if __name__ == '__main__':
    n = int(input())
    print(solve('{}\n'.format(n)+'\n'.join([input() for _ in range(n)])))

Submission status: Accepted

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

def solve(N: int, x: "List[int]", y: "List[int]"):
    sum = 0
    kumi = list(itertools.permutations(range(N), N))
    for item in kumi:
        for i in range(N-1):
            a = item[i]
            b = item[i+1]
            hoge = math.sqrt((x[a]-x[b])**2 + (y[a]-y[b])**2)
            sum += hoge
    print(sum/len(kumi))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

n = int(input())

cities = []
for i in range(n):
  cities.append(tuple(map(int, input().split())))
  
score = 0
for i in range(n-1):
  city1 = cities[i]
  for j in range(i+1, n):
    city2 = cities[j]
    distance = math.sqrt(
      (city1[0] - city2[0]) ** 2 + \
      (city1[1] - city2[1]) ** 2
    )
    score += distance
    
print(2 * score / n)

Submission status: Accepted

Solution code:
import itertools
import math
N = int(input())
rs = [list(map(int, input().split())) for _ in range(N)]
total = 0
for p in list(itertools.permutations(range(N))):
    dist = 0
    start = rs[p[0]]
    for i in p[1:]:
        dist += ((rs[i][0] - start[0]) ** 2 + (rs[i][1] - start[1]) ** 2 ) ** (1/2)
        start = rs[i]
    total += dist
print(total / math.factorial(N))

Submission status: Accepted

Solution code:
import math
import itertools

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

def calc(a,b):
    x1, y1 = a
    x2, y2 = b
    return math.sqrt((x1-x2)**2 +(y1 - y2)**2)

ans = 0

for order in itertools.permutations(range(N)):
    tmp = 0
    for i in range(1,N):
        tmp += calc((xy[order[i]]), (xy[order[i-1]]))
    ans += tmp

ans /= math.factorial(N)

print(ans)

Submission status: Accepted

Solution code:
from __future__ import print_function

import sys
input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

from pprint import pprint
import math
# import string
# import fractions
# from fractions import Fraction
# from fractions import gcd

# def lcm(n,m):
#     return int(n*m/gcd(n,m))

# import re
# import array
# import copy
# import functools
# import operator

# import collections
import itertools
# import bisect
# import heapq


# from heapq import heappush
# from heapq import heappop
# from heapq import heappushpop
# from heapq import heapify
# from heapq import heapreplace

# from queue import PriorityQueue as pq

# def reduce(p, q):
#     common = fractions.gcd(p, q)
#     return (p//common , q//common )
# # from itertools import accumulate
# # from collections import deque

# from operator import mul
# from functools import reduce

# def combinations_count(n, r):
#     r = min(r, n - r)
#     numer = reduce(mul, range(n, n - r, -1), 1)
#     denom = reduce(mul, range(1, r + 1), 1)
#     return numer // denom

# import random

def main():
    n = int(input().strip())
    l_xy=[]
    for i in range(n):
        x,y = map(int, input().strip().split())
        l_xy.append([x,y])
    #epint("l_xy ",end=":\n")
    #epint(l_xy,width=20)

    sum_distance= 0 #for _ in range(math.factorial(n))]
    i_cnt=0
    for l_route in itertools.permutations(l_xy):
        #epint("l_route ",end=": ")
        #epint(l_route)
        distance=0
        for i in range(1,len(l_route)):
            distance+=math.sqrt((l_route[i][1] - l_route[i-1][1])**2 + (l_route[i][0] - l_route[i-1][0])**2)
        sum_distance+=distance
        i_cnt+=1
        # hoge
    ans=sum_distance/math.factorial(n)
    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import copy
input = sys.stdin.readline
N = int(input())
ans = 0
xy = [list(map(int, input().split())) for i in range(N)]


def maken(n):
    s = 1
    for i in range(1, n+1):
        s *= i
    return s


for i in range(N):
    xy2 = copy.deepcopy(xy)
    c = xy2[i]
    del xy2[i]
    for l in xy2:
        ans += (((c[0]-l[0])**2+(c[1]-l[1])**2)**(1/2))*(maken(N-1))
print(ans/maken(N))

Submission status: Accepted

Solution code:
def permutation(lst):
    if len(lst) == 0:
        return []
    if len(lst) == 1:
        return [lst]
    res = []
    for i in range(len(lst)):
       m = lst[i]
       remLst = lst[:i] + lst[i+1:]
       for p in permutation(remLst):
           res.append([m] + p)
    return res

dist = lambda x1, y1, x2, y2 : ((x1-x2)**2 + (y1-y2)**2)**.5
n = int(input())
d = [[0] * n for _ in range(n)]
pnts = []
for _ in range(n):
	x, y = map(int, input().split())
	pnts.append((x, y))
for i in range(n):
	for j in range(n):
		d[i][j] = d[j][i] = dist(pnts[i][0], pnts[i][1], pnts[j][0], pnts[j][1])
paths = permutation(list(range(n)))
res = 0
for path in paths:
    for j in range(n-1):
        res += d[path[j]][path[j+1]]
print(round(res/len(paths), 6))

Submission status: Accepted

Solution code:
n = int(input())
towns = []
for _ in range(n):
  towns.append([int(x) for x in input().split()])

import math
import itertools
patterns = list(itertools.permutations(range(n)))

length = 0
for pattern in patterns:
  for i in range(n-1):
    p = pattern[i]
    pp = pattern[i+1]
    length += math.sqrt((towns[p][0]-towns[pp][0])**2 + (towns[p][1]-towns[pp][1])**2)

print(length/len(patterns))

Submission status: Accepted

Solution code:
from itertools import *
from math import *

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

total_cost = 0
count = 0
for perm in permutations(range(N)):
    count += 1

    for i in range(len(perm) - 1):
        pi, pj = perm[i], perm[i + 1]
        dij = sqrt((x[pi] - x[pj]) ** 2 + (y[pi] - y[pj]) ** 2)
        total_cost += dij
    # print(perm)

print("{:.10f}".format(total_cost / count))

Submission status: Accepted

Solution code:
import math
N = int(input())
p = []
for n in range(0,N):
  x,y = map(int, input().split(" "))
  p.append((x,y))

sum = 0
for i in range(0,N):
  for j in range(0,N):
    #print(math.sqrt( (p[i][0]-p[j][0])**2 + (p[i][1]-p[j][1])**2 ))
    sum += math.sqrt( (p[i][0]-p[j][0])**2 + (p[i][1]-p[j][1])**2 )
print(sum/N)

Submission status: Accepted

Solution code:
n=int(input())
x=[]
y=[]
ans=0
for i in range(n):
  a,b=map(int,input().split())
  x.append(a)
  y.append(b)
for p in range(n-1):
  for q in range(p+1,n):
    ans += (((x[p]-x[q])**2+(y[p]-y[q])**2)**0.5)*2/n
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N=int(input())

X=np.zeros(N)
Y=np.zeros(N)

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

XX = np.tile(X, (N, 1))
YY = np.tile(Y, (N, 1))

dX = XX - XX.T
dY = YY - YY.T

norm=(dX**2 + dY**2)**0.5

#print(X)
#print(Y)
#print(dX)
#print(dY)
#print(norm)

ans=sum(norm.reshape(-1))/N
print(ans)