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:
#!/usr/bin/env python3
import sys
from itertools import permutations

def solve(N: int, x: "List[int]", y: "List[int]"):
    def d(xy1_xy2):
        xy1, xy2 = xy1_xy2
        return ((xy1[0] - xy2[0]) ** 2 + (xy1[1] - xy2[1]) ** 2) ** 0.5

    acc = [sum(map(d, zip(perm, perm[1:]))) for perm in map(tuple, permutations(zip(x, y)))]
    return sum(acc) / len(acc)

# 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))
    print(solve(N, x, y))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

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

permutations_lis = itertools.permutations(range(n))# 全ての場合のリストを生成
dis_list = []
for case in permutations_lis:
    dis_sum = 0
    for i in range(n-1):
        dis_sum += dis(coor[case[i]], coor[case[i+1]])
    dis_list.append(dis_sum)

print(np.mean(dis_list))

Submission status: Accepted

Solution code:
import itertools
n = int(input())
xy = []
for i in range(n):
    xy.append(list(map(int, input().split())))
per = list(itertools.permutations([i for i in range(n)]))
dist = 0
for i in per:
    for j in range(len(i)-1):
        xi = xy[i[j]][0]
        yi = xy[i[j]][1]
        xj = xy[i[j+1]][0]
        yj = xy[i[j+1]][1]
        dist += ((xi - xj) ** 2 + (yi - yj) ** 2) ** 0.5
dist /= len(per)
print(dist)

Submission status: Accepted

Solution code:
import itertools
import sys
input = sys.stdin.readline

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

    perms = list(itertools.permutations(range(N), N))
    l = 0
    for v in perms:
        for i in range(N-1):
            xi, yi = cities[v[i]]
            xj, yj = cities[v[i+1]]

            l += ((xi - xj) ** 2 + (yi - yj) ** 2) ** 0.5

    ans = l / len(perms)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import itertools

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

pattern = list(range(N))
patterns = list(itertools.permutations(pattern))

for pattern in patterns:
    tmp_dist = 0
    for i in range(N - 1):
        x, y = points[pattern[i]]
        nx, ny = points[pattern[i + 1]]
        tmp_dist += ((nx - x) ** 2 + (ny - y) ** 2) ** 0.5
    sum_dist += tmp_dist

print(sum_dist / len(patterns))

Submission status: Accepted

Solution code:
N = int(input())
p = [list(map(int, input().split())) for _ in range(N)]
table = [[0] * N for _ in range(N)]
for i in range(N-1):
  for j in range(i+1, N):
    table[i][j] = table[j][i] = ((p[i][0] - p[j][0]) ** 2 + (p[i][1] - p[j][1]) ** 2) ** 0.5

dist = 0
cnt = 0
import itertools
for permutation in itertools.permutations(list(range(N))):
  i = 0
  while i < N - 1:
    dist += table[permutation[i]][permutation[i+1]]
    i += 1
  cnt += 1
print(dist / cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import itertools
import math

N = int(input())
towns = []
for i in range(N):
    l = list(map(int, input().split()))
    towns.append(l)
# print(N, towns)

paths = list(map(list, itertools.permutations(range(N), N)))
# print(paths)

dists = []
for path in paths:
    dist = 0
    for i, v in enumerate(path):
        town = towns[v]
        if i != N - 1:
            town_next = towns[path[i+1]]
            # print(i)
            # print(town)
            # print(town_next)
            x1, y1 = town[0], town[1]
            x2, y2 = town_next[0], town_next[1]
            dist += math.sqrt((x1 - x2)**2 + (y1 - y2)**2)
    dists.append(dist)

# print(dists)
print(sum(dists)/len(dists))

Submission status: Accepted

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

res = 0

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


print(res*2/N)

Submission status: Accepted

Solution code:
import math
import itertools
n = int(input())
info = []
for i in range(n):
    x, y = map(int, input().split())
    info.append([i, x, y])
num = [i for i in range(n)]
# print(info, num)
ans = 0

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

for v in itertools.permutations(num):
    # print(v)
    for i in range(n-1):
        ans += d(info[v[i]][1], info[v[i+1]][1], info[v[i]][2], info[v[i+1]][2])

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
import math

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

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

dists = []
for item in itertools.permutations(range(n)):
    tmp = 0
    for i in range(n-1):
        tmp += dist(item[i], item[i+1])
    dists.append(tmp)

print(sum(dists) / len(dists))

Submission status: Accepted

Solution code:
# from fractions import gcd
# mod = 10 ** 9 + 7
# N = int(input())
# a = list(map(int,input().split()))
# a,b,c = map(int,input().split())
# ans = [0] * N
# math.ceilで切り上げ
# dp = [[0] * 4 for i in range(3)] #2次元配列初期化
# dp = [[[0] * 2 for i in range(3)] for j in range(5)]
# (ord('A'))でASCII出力 Aは65
import math
import numpy as np
import statistics
import string
import sys
from array import array
from collections import deque

def intinput():
    return int(input())
def listintinput():
    return list(map(int, input().split()))
def splitintinput():
    return map(int, input().split())
def factorialsurplus(x, y, z):  # xからyまでの階乗をzで割ったあまりを求める
    ret = 1
    for i in range(x, y + 1):
        ret = (ret * i) % z
    return (ret)
def isprime(x):
    if x == 1:
        return False
    if x == 2:
        return True
    sq = int(math.sqrt(x))
    for i in range(2,sq+1):
        if x % i == 0:
            return False
    return True
def hcfnaive(a,b):#最大公約数 math.gcdが使えない時の手段として入れとく。pythonが更新されたらいらなくなるはず
    if(b==0):
        return a
    else:
        return hcfnaive(b,a%b)

N = intinput()
ans = 0
tmp = []
sum = 0
for i in range(N):
    a = np.array(listintinput())
    for j in tmp:
       sum += np.linalg.norm(a-j)
    tmp.append(a)

print(sum*(N-1)/(N*(N-1)/2))

Submission status: Accepted

Solution code:
import math

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

D=[]
for i in range(n-1):
    for j in range(i+1,n):
        D.append(math.sqrt((M[i][0]-M[j][0])**2+(M[i][1]-M[j][1])**2))

print(sum(D)*2/n)

Submission status: Accepted

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

N = int(input())
point = defaultdict(list)
for i in range(1, N+1):
    x, y = list(map(int, input().split()))
    point[i] = [x, y]

res = 0
for permutation in permutations(range(1, N+1)):
    for i in range(1, N):
        nx, pre = permutation[i], permutation[i-1]
        res += sqrt( pow((point[nx][0] - point[pre][0]), 2) + pow((point[nx][1] - point[pre][1]), 2) )

print(res / factorial(N))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect_left

def main():
    n=int(input())
    xy=[list(map(int,input().split())) for _ in range(n)]
    ans=0
    for i in range(n-1):
        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/=n/2
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()

A = [tuple(int(i) for i in input().split()) for _ in range(n)]

memo = [[-1]*n for i in range(n)]
keiro_sum = 0

cnt = 0
for i in itertools.permutations(range(n)):
    cnt += 1
    one_root = 0
    for j in range(1,n):
        if(memo[i[j-1]][i[j]] == -1):
            distance = ((A[i[j]][0] - A[i[j-1]][0])**2 + (A[i[j]][1] - A[i[j-1]][1])**2)**0.5
            memo[i[j]][i[j-1]] = distance
            memo[i[j-1]][i[j]] = distance
        else:
            distance = memo[i[j-1]][i[j]]
        one_root += distance

    keiro_sum += one_root

print(keiro_sum/cnt)

Submission status: Accepted

Solution code:
import itertools
import math

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

next_p = itertools.permutations(a)
total = 0
for p in next_p:
  for i in range(n - 1):
    temp = (p[i][0] - p[i + 1][0]) ** 2 + (p[i][1] - p[i + 1][1]) ** 2
    total += math.sqrt(temp)


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

Submission status: Accepted

Solution code:

from itertools import permutations
import math


def submit():
    n = int(input())
    positions = {i: tuple(map(int, input().split())) for i in range(n)}
    cities = [i for i in range(n)]
    
    dists = {}
    for i in cities[:-1]:
        for j in cities[i + 1:]:
            pi = positions[i]
            pj = positions[j]
            d = math.sqrt((pi[0] - pj[0]) ** 2 + (pi[1] - pj[1]) ** 2)
            dists[(i, j)] = d
            dists[(j, i)] = d

    path_count = 0
    path_sum = 0
    for p in permutations(cities):
        d = 0
        for i in range(n - 1):
            d += dists[(p[i], p[i + 1])]
        path_sum += d
        path_count += 1

    print(path_sum / path_count)


if __name__ == "__main__":
    submit()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import math

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

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

print(2*L/N)

Submission status: Accepted

Solution code:
import itertools

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

ans = 0
for t in itertools.permutations(x):
    for i in range(n-1) :
      ans += ((t[i][0]-t[i+1][0])**2+(t[i][1]-t[i+1][1])**2)**0.5

print(ans/max)

Submission status: Accepted

Solution code:
from math import factorial,sqrt
from itertools import permutations as permus
# from fractions import gcd
# from collections import deque,Counter

import numpy as np
# import scipy as scp

# 入力の受け取り
n = int(input())
# 列ベクトルとかの受け取り
times = n
lists = []
for _ in range(times):
    lists.append(list(map(int,input().split())))  #table.append(input())とも書ける

# print(lists)
routes = list(permus(range(0,n)))
# print(len(routes))
res = 0
for rout in routes:
    for i,town in enumerate(rout):
        if i == 0:
            continue
        else:
            xi = lists[rout[i]][0]
            yi = lists[rout[i]][1]
            xj = lists[rout[i-1]][0]
            yj = lists[rout[i-1]][1]
            res += sqrt((xi -xj)**2 + (yi-yj)**2)

ans = res/len(routes)

print("{:.10f}".format(ans))

Submission status: Accepted

Solution code:
import itertools
import math

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

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

conut=[i for i in range(N)]
conb=itertools.permutations(conut, N)
total=0
for n,c in enumerate(conb):
    for i in range(N-1):
        n1=c[i]
        n2=c[i+1]
        h=math.sqrt((x[n1]-x[n2])**2 + (y[n1]-y[n2])**2)
        total+=h

print(total/(n+1))

Submission status: Accepted

Solution code:
def resolve():
    import math
    n = int(input())
    distance = [list(map(int, input().split())) for i in range(n)]
    c =[[0]*n for i in range(n)]
    for i in range(n):
        for j in range(n):
            dix = (distance[i][0] - distance[j][0]) **2
            diy = (distance[i][1] - distance[j][1]) **2
            c[i][j] = (dix+diy)**0.5
    sumc = 0
    for i in range(n):
        sumc += sum(c[i])
    print(sumc/n)
resolve()

Submission status: Accepted

Solution code:
import math

n = int(input())
s_amount = 0

l = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
  for j in range(i):
    s_amount += math.sqrt((l[i][0] - l[j][0]) ** 2 + (l[i][1] - l[j][1]) ** 2)
    
print(s_amount / sum([i for i in range(n)]) * (n-1))

Submission status: Accepted

Solution code:
import itertools

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

# print(cities)

distances = []
for i in range(8):
    distances.append([0. for j in range(8)])

for i in range(n):
    for j in range(i + 1, n):
        x = cities[i][0] - cities[j][0]
        y = cities[i][1] - cities[j][1]
        d = (x **2 + y ** 2) ** 0.5
        distances[i][j] = d
        distances[j][i] = d
# print(distances)

order_cnt = 0
sum_distance = 0.0
for order in itertools.permutations(range(n)):
    # print(order)
    current_distance = 0
    for i in range(len(order) - 1):
        current_distance += distances[order[i]][order[i + 1]]
    # print(current_distance)
    order_cnt += 1
    sum_distance += current_distance

print(sum_distance / order_cnt)

Submission status: Accepted

Solution code:
import itertools

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

fact = [1] * (N + 1)
for i in range(1, N + 1):
    fact[i] = fact[i-1] * i


def L2norm(i, j):
    X = XY[i][0] - XY[j][0]
    Y = XY[i][1] - XY[j][1]
    return (X**2 + Y**2) ** (1/2)


dist = [[0] * N for i in range(N)]
for i in range(N):
    for j in range(i, N):
        r = L2norm(i, j)
        dist[i][j] = r
        dist[j][i] = r

ans = 0
stock = 0
for perm in itertools.permutations(range(N), N):
    cur = 0
    for i in range(N-1):
        cur += dist[perm[i]][perm[i+1]]
    ans += cur
print(ans/fact[N])

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt

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

for n in range(N):
    xi, yi = map(int, input().split())
    x.append(xi)
    y.append(yi)

for i in permutations(range(N)):
    d = 0
    for j in range(len(i) - 1):
        d += sqrt((x[i[j]] - x[i[j + 1]])**2 + (y[i[j]] - y[i[j + 1]])**2)
    dist.append(d)

print(sum(dist) / len(dist))

Submission status: Accepted

Solution code:
import numpy as np
import itertools

def calc_distance(p1,p2):
    dis = ((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)**0.5
    return dis

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


distance_list = []
for route in itertools.permutations(range(n)):
    total = 0
    for j in range(len(route) - 1):
        d = calc_distance(data[route[j]], data[route[j+1]])
        #dis = ((data[route[j]][0] - data[route[j+1]][0])**2 + (data[route[j]][1] - data[route[j+1]][1])**2)**0.5
        total += d
    distance_list.append(total)

print(np.mean(distance_list))

Submission status: Accepted

Solution code:
import itertools, math

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

routes = itertools.permutations(shops, N)
l = list(routes)

total = 0
for route in l:
    tmp = 0
    for i in range(1,len(route)):
        kyori = (route[i][0]-route[i-1][0])**2 + (route[i][1]-route[i-1][1])**2
        tmp += math.sqrt(kyori)
    total += tmp
ans = total/len(l)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import permutations

def solve():
    N = int(input())
    A = []
    for _ in range(N):
        a, b = list(map(int, input().split()))
        A.append([a, b])
    l = list(permutations(A))
    s = 0
    for t in l:
        for i in range(N-1):
            a, b = t[i]
            c, d = t[i+1]
            s = s + ((a-c)**2 + (b-d)**2) ** 0.5
    return s / len(l)

print(solve())

Submission status: Accepted

Solution code:
n = int(input())
L = []
for i in range(n):
    a,b = map(int,input().split())
    L.append([a,b])
import itertools
def dis(p,q,r,s):
    return ((p-r)**2 + (q-s)**2)**0.5
ans = 0
cnt1 = 0
for v in itertools.permutations(L):
    cnt1 +=1
    for i in range(n-1):
        ans +=dis(v[i][0],v[i][1],v[i+1][0],v[i+1][1])
print(ans/cnt1)

Submission status: Accepted

Solution code:
#abc129 c
import math
import itertools
n=int(input())
zahyo=[]
for i in range(n):
    line=list(map(int,input().split()))
    zahyo.append(line)
num=[i for i in range(n)]
patarn=list(itertools.permutations(num))
#print(patarn)

def siwu(x,keta):
    x=x*10**keta
    if (x*10)%10>=5:
        x+=1
    x=int(x)
    x/=10**keta
    return x


def kyori(xy1,xy2):
    x1,y1=xy1
    x2,y2=xy2
    s=math.sqrt((x1-x2)**2+(y1-y2)**2)
    return s
ans=0
for i in patarn:
    s=0
    for j in range(n-1):
        s+=kyori(zahyo[i[j]],zahyo[i[j+1]])
    ans+=s
ans/=len(patarn)
#ans=siwu(ans,6)
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math

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

def dist(x0,y0,x1,y1):
    return math.sqrt((x0-x1)**2+(y0-y1)**2)

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

distsum = 0
for i in range(len(Pt)):
    for j in range(N-1):
        distsum += dist(C[Pt[i][j]][0],C[Pt[i][j]][1],C[Pt[i][j+1]][0],C[Pt[i][j+1]][1])

print(distsum / len(Pt))

Submission status: Accepted

Solution code:
from itertools import permutations
import statistics

N = int(input())
box = [list(map(int, input().split())) for _ in range(N)]
p_box = permutations(box)
ans = []
for i in p_box:
    temp = 0
    for j in range(1, N):
        temp += ((i[j][0] - i[j-1][0])**2 + (i[j][1] - i[j-1][1])**2)**(1/2)
    ans.append(temp)

print(statistics.mean(ans))

Submission status: Accepted

Solution code:
import itertools
import math

N = int(input())
nums = [i for i in range(N)]
town = []
distance = {}
d_sum = 0

for _ in range(N):
    town.append(list(map(int, input().split())))
    
for i in range(N):
    for j in range(i + 1, N):
        key = str(i) + "_" + str(j)
        distance[key] = (math.sqrt((town[i][0] - town[j][0]) ** 2 + (town[i][1] - town[j][1]) ** 2 ))

for v in itertools.permutations(nums, N):
    for i in range(N -1):
        if v[i] > v[i + 1]:
            key = str(v[i + 1]) + "_" + str(v[i])
        else:
             key = str(v[i]) + "_" + str(v[i + 1])
        d_sum += distance[key]

print(d_sum / math.factorial(N))

Submission status: Accepted

Solution code:
import itertools
import math
n = int(input())
l = list(itertools.permutations(range(n)))
X = []
Y = []
for i in range(n):
  x,y = map(int,input().split())
  X.append(x)
  Y.append(y)
result = []
for i in l:
  #print(i)
  d = 0
  for j in range(int(len(i))-1):
    d += math.sqrt((X[i[j]]-X[i[j+1]])**2 + (Y[i[j]]-Y[i[j+1]])**2)
    #print(d)
  result.append(d)
print(sum(result)/len(result))

Submission status: Accepted

Solution code:
import itertools
n = int(input())
l = []
for i in range(n):
    x,y = map(int, input().split())
    l.append((x, y))
perm = list(itertools.permutations(range(n),n))
ans = 0
for p in perm:
    for i in range(n-1):
        ans += ((l[p[i]][0] - l[p[i+1]][0])**2 +(l[p[i]][1] - l[p[i+1]][1])**2)**0.5
ans /=len(perm)
print(ans)

Submission status: Accepted

Solution code:
import math
import itertools

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 i in range(N)]
for i in range(N):
  for j in range(N):
    D[i][j] = ((x[i]-x[j])**2+(y[i]-y[j])**2)**0.5
P = list(itertools.permutations(list(range(N)),N))
dist = [0]*len(P)
for j, p in enumerate(P):
  for i in range(N-1):
    dist[j] += D[p[i]][p[i+1]]
ave = sum(dist)/len(P)
print(ave)

Submission status: Accepted

Solution code:
import itertools
import math
n = int(input())
x_y = [list(map(int, input().split())) for _ in range(n)]
ans = 0
perm = itertools.permutations(range(n))
for p in perm:
    for i in range(n - 1):
        pos = p[i]
        next_pos = p[i + 1]
        ans += ((x_y[pos][0] - x_y[next_pos][0]) ** 2 + (x_y[pos][1] - x_y[next_pos][1]) ** 2) ** (1/2)
print(ans / math.factorial(n))

Submission status: Accepted

Solution code:
import itertools
from math import sqrt
def main():
    def helper():
        pass
    def dist(p1, p2):
        dX, dY = p1[0]-p2[0], p1[1]-p2[1]
        return sqrt(dX*dX+dY*dY)

    N = int(input())
    P = []
    for _ in range(N):
        x, y = map(int, input().split())
        P.append((x, y))
    
    D = []
    ct = 0
    for p_list in itertools.permutations(P, N):
        ct += 1
        d = 0
        for i in range(len(p_list)-1):
            d += dist(p_list[i], p_list[i+1])
        D.append(d)
    print(sum(D)/ct)

main()

Submission status: Accepted

Solution code:
def dist(x, y):
    return ((x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2) ** .5

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

d = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        d += dist(lst[i], lst[j])

print(d * 2 / N)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Mar 10 20:52:06 2020

@author: Kanaru Sato
"""
import math

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

sum_d = 0

for i in range(0,n):
    for j in range(0,n):
        d_sq = (cities[i][0]-cities[j][0])**2+(cities[i][1]-cities[j][1])**2
        sum_d = sum_d + math.sqrt(d_sq)

print(sum_d/n)

Submission status: Accepted

Solution code:
import math
import itertools

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

arr = list(range(n))
p = list(itertools.permutations(arr))

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

ans = []

for p_arr in p:
    s = 0.0
    for i in range(1,len(p_arr)):
        s += calc(x[p_arr[i]],y[p_arr[i]],x[p_arr[i-1]],y[p_arr[i-1]])
    ans.append(s)

print(sum(ans) / len(ans))

Submission status: Accepted

Solution code:
from itertools import permutations
import math

n = int(input())
arr = [tuple(map(int, input().split())) for _ in range(n)]
total = 0
for v in permutations(arr, n):
    d = 0
    for i in range(n-1):
        x1, y1 = v[i]
        x2, y2 = v[i+1]
        d += math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
    total += d
print(total / math.factorial(n))

Submission status: Accepted

Solution code:
import itertools as it
n = int(input())
zahyou = []
for i in range(n):
    x,y = map(int, input().split())
    zahyou.append((x,y))
perm = list(it.permutations(range(n),n))
ans = 0
for zyu in perm:
    for i in range(n-1):
        ans += ((zahyou[zyu[i]][0] - zahyou[zyu[i+1]][0])**2 +(zahyou[zyu[i]][1] - zahyou[zyu[i+1]][1])**2 )**.5
ans /=len(perm)
print(ans)

Submission status: Accepted

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

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

def sumdis(m):
  res = 0
  for i in range(0,n-1):
    for j in range(i+1,n):
      res += dis(m[i], m[j])
  return res*2/n

print(sumdis(List))

Submission status: Accepted

Solution code:
import math
import itertools

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

P = itertools.permutations(range(N))
ans = []
for p in P:
    s = 0
    for i in range(len(p) - 1):
        s += math.sqrt(
            math.pow(c[p[i]][0] - c[p[i + 1]][0], 2)
            + math.pow(c[p[i]][1] - c[p[i + 1]][1], 2)
        )
    ans.append(s)

print(sum(ans) / len(ans))

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    xy = [tuple(map(int, input().split())) for _ in range(N)]
    def dist(xy1,xy2): return ((xy1[0]-xy2[0])**2 + (xy1[1]-xy2[1])**2)**0.5
    ans = 0
    for i in range(N):
        for j in range(i+1,N):
            ans += dist(xy[i],xy[j])
    print(ans*2/N)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import permutations

n = int(input())
x, y = zip(*[list(map(int, input().split()))for i in range(n)])
ans = cnt = 0
for i in permutations(range(n)):
        cnt += 1
        for j in range(n-1):
                f, t = i[j], i[j+1]
                ans += ((x[f]-x[t])**2 + (y[f]-y[t])**2)**0.5
print(ans/cnt)

Submission status: Accepted

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

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

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

print(ans / fact(N))

Submission status: Accepted

Solution code:
import math
N=int(input())#数字のinputはintつけよう
x=[0]*N
y=[0]*N
for i in range(0,N):
    x[i],y[i]=map(int,input().split())
sum=0
count=0
for i in range(0,N):
    for j in range(0,N):
        sum+=math.sqrt((x[i]-x[j])**2+(y[i]-y[j])**2)
        count+=1
print(sum*N/count)

Submission status: Accepted

Solution code:
from fractions import gcd
from math import sqrt
from collections import deque,defaultdict,Counter
from heapq import heapify,heappop,heappush
from copy import deepcopy
from itertools import accumulate,permutations
from bisect import bisect_left,bisect_right

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

states = list(permutations(list(range(N))))

ans = 0
for state in states:
    x,y = xy[state[0]]
    dist = 0
    for i in state[1:]:
        nx,ny = xy[i]
        dist += sqrt(pow(nx - x, 2) + pow(ny - y, 2))
        x,y = nx,ny
    ans += dist

print(ans / len(states))

Submission status: Accepted

Solution code:
import sys
from math import sqrt
from itertools import permutations as permi
input = sys.stdin.readline
N = int(input())
ps = []
for _ in range(N): 
  u, v = map(int, input().split())
  ps.append((u, v))
res = 0
c = 0
for p in permi([x for x in range(N)], N):
  t = 0
  c += 1
  for i in range(N - 1):
    x = p[i]
    y = p[i + 1]
    t += sqrt((ps[x][0] - ps[y][0]) ** 2 + (ps[y][1] - ps[x][1]) ** 2)
  #print(t, p)
  res += t
print(res / c)

Submission status: Accepted

Solution code:
import sys
from itertools import permutations
def main():
    input = sys.stdin.readline
    N = int(input())
    xy = [tuple(map(int, input().split())) for _ in range(N)]
    def dist(x1,y1,x2,y2): return ((x1-x2)**2 + (y1-y2)**2)**0.5
    ans = 0
    for route in permutations(range(N)):
        for i in range(N-1):
            ans += dist(xy[route[i]][0],xy[route[i]][1],xy[route[i+1]][0],xy[route[i+1]][1])
    for i in range(1,N+1):
        ans /= i
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import permutations

def fact(n):
    if n == 0:
        return 1
    return n * fact(n-1)

N = int(input())
xy = [tuple(map(int, input().split())) for _ in range(N)]
s = 0
for p in permutations(list(range(N))):
    for i in range(N-1):
        dx = xy[p[i+1]][0] - xy[p[i]][0]
        dy = xy[p[i+1]][1] - xy[p[i]][1]
        s += (dx**2+dy**2)**.5
print(s/fact(N))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    ans = 0
    from itertools import permutations
    from math import hypot
    XY = [[int(i) for i in input().split()] for j in range(N)]
    for p in permutations(range(N)):
        cur = 0
        for i in range(N-1):
            cur += hypot(XY[p[i]][0] - XY[p[i+1]][0],
                         XY[p[i]][1] - XY[p[i+1]][1])
        ans += cur
    fact = 1
    for i in range(1, N+1):
        fact *= i
    print(ans / fact)


if __name__ == '__main__':
    main()