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: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

N = int(input().strip())
p = []
for n in range(N):
  i = list(map(int, input().strip().split(' ')))
  #p.append(i)
  p.append(np.array(i))

l = list(itertools.permutations(p, N))
#print(l)

sum = 0
for l1 in l:
  j = 0
  while j < N - 1:
    sum += np.linalg.norm(l1[j] - l1[j + 1])
    j += 1
print(sum / len(l))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import permutations

n = int(input())

li = []
for _ in range(n):
    i, j = map(int, input().split())
    li.append(np.array([i, j]))

li2 = permutations(li)

re = []
for a in li2:
    dis = [np.linalg.norm(a[i] - a[i+1]) for i in range(n-1)]
    re.append(sum(dis))

print(np.average(re))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import math
N = int(input())
x = [list(map(int, input().split())) for _ in range(N)]
nlst = '01234567'
xlst = []
a = [-1] * N
def dfs(cnt):
    if cnt == N:
        tmpF = True
        for i in range(N):
            if a.count(int(nlst[i])) != 1:
                tmpF = False
                break
        if tmpF:
            tmp = 0
            for i in range(1, N):
                tmp += math.sqrt(((x[a[i - 1]][0] - x[a[i]][0]) ** 2) + (x[a[i - 1]][1] - x[a[i]][1]) ** 2)
            xlst.append(tmp)
        return

    for i in range(N):
        a[cnt] = i
        dfs(cnt + 1)

dfs(0)

kain = 1
for i in range(1, N + 1):
    kain *= i

print(sum(xlst) / kain)

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
x = [list(map(int, input().split())) for _ in range(N)]
nlst = '01234567'
xlst = []
a = [-1] * N
def dfs(cnt):
    if cnt == N:
        tmpF = True
        for i in range(N):
            if a.count(int(nlst[i])) != 1:
                tmpF = False
                break
        if tmpF:
            tmp = 0
            for i in range(1, N):
                tmp += math.sqrt(((x[a[i - 1]][0] - x[a[i]][0]) ** 2) + (x[a[i - 1]][1] - x[a[i]][1]) ** 2)
            xlst.append(tmp)
        return

    for i in range(N):
        a[cnt] = i
        dfs(cnt + 1)

dfs(0)

kain = 1
for i in range(1, N + 1):
    kain *= i

print(sum(xlst) / kain)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import permutations
N = int(input())
coodinate = []
for _ in range(N):
    x , y = map(int,input().split())
    coodinate.append([x,y])
coodinate = np.array(coodinate)
distance = []
for val in permutations(coodinate):
    now_distance = 0
    for i in range(N-1):
        now_distance += np.linalg.norm(val[i+1] - val[i])
    distance.append(now_distance)
print(sum(distance) / len(distance))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools

n = int(input())

route = [np.array(list(map(int, input().split()))) for _ in range(n)]
results = []
for v in itertools.permutations(route, r=n):
    distance = 0
    for start, goal in zip(v[:-1], v[1:]):
        distance += np.linalg.norm(goal - start)
    results.append(distance)
print(np.mean(results))

Submission status: Accepted

Solution code:
import itertools

N = int(input())
X = []
Y = []
seq = list(itertools.permutations([i for i in range(1,N+1)]))
a = 0
for i in range(N):
    x,y = map(int,input().split())
    X.append(x)
    Y.append(y)
for h in range(len(seq)):
    for i in range(N-1):
        a += ((X[seq[h][i]-1]-X[seq[h][i+1]-1])**2+(Y[seq[h][i]-1]-Y[seq[h][i+1]-1])**2)**0.5
print(a/len(seq))

Submission status: Accepted

Solution code:
import itertools
import math

n = int(input())
xy = [0]*n

for i in range(n):
  xy[i] = input().split()

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

t = list(itertools.permutations(t))
ans = 0

for i in range(len(t)):
  for j in range(n-1):
    tmp = t[i][j]
    tmp2 = t[i][j+1]
    ans += math.sqrt(((int(xy[tmp][0]) - int(xy[tmp2][0]))**2) + ((int(xy[tmp][1]) - int(xy[tmp2][1]))**2))
    
print(ans/len(t))

Submission status: Accepted

Solution code:
N = int(input())
D = [list(map(int, input().split())) for _ in range(N)]
from math import hypot, factorial
distance = []

for i, j in D:
    for k, l in D:
        distance.append(hypot(i-k, j-l))

print(sum(distance)/N)

Submission status: Accepted

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

def main():
    lists = []
    N= int(input())
    lists=[list(map(int,input().split())) for _ in range(N)]
    ans=0
    length=0
    #permutationsは順列を列挙
    for line in itertools.permutations(lists):
        a = []
        b = []
        for data in line:
            if len(b) ==0:
                b = data
                continue
            else:
                a = b
                b = data
                length = math.sqrt(((b[0]-a[0])**2)+((b[1]-a[1])**2))
                ans+=length
    #factorical=階上の値
    print(ans/math.factorial(N))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
x_y = [ list(map(int, input().split())) for _ in range(n)  ]
import math
d = []
for i in range(n):
    for j in range(n):
        if i != j:
            x1, y1 = x_y[i]
            x2, y2 = x_y[j]
            d.append(math.sqrt((x1-x2)**2+(y1-y2)**2))
print(sum(d)/n)

Submission status: Accepted

Solution code:
import itertools, math
N = int(input())
ls, L = [], 0
for i in range(N):
    x, y = map(int, input().split(' '))
    ls.append([x, y])
perms = itertools.permutations(range(N))
for perm in perms:
    for i in range(N - 1):
        L += math.sqrt((ls[perm[i + 1]][0] - ls[perm[i]][0]) ** 2 + (ls[perm[i + 1]][1] - ls[perm[i]][1]) ** 2)
print(L / math.factorial(N))

Submission status: Accepted

Solution code:
from collections import deque

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

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

que = deque([[i] for i in range(N)])
perm = []
while que:
  seq = que.popleft()
  if len(seq) == N:
    perm.append(seq)
  for j in range(N):
    if j not in seq:
      que.append(seq + [j])

d = 0
s = len(perm)
for p in perm:
  for k in range(N-1):
    d += dist(xy[p[k]], xy[p[k+1]])
print(d / s)

Submission status: Accepted

Solution code:
import math
import itertools


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


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

for _ in range(N):
    addresses.append(list(map(int, input().split())))

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

ans = 0
for x in ways:
    dist = 0
    for i in range(N - 1):
        dist += calc(addresses[x[i]], addresses[x[i + 1]])
    ans += dist

print(ans / len(ways))

Submission status: Accepted

Solution code:
from itertools import permutations
import math
n=int(input())
G=[]
for _ in range(n):
  x,y=map(int,input().split())
  G.append([x,y])
  
ans=0 
for v in permutations(range(n),n):
  for i in range(n-1):
    ans+=((G[v[i]][0]-G[v[i+1]][0])**2+(G[v[i]][1]-G[v[i+1]][1])**2)**0.5
    

print(ans/math.factorial(n))

Submission status: Accepted

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

def main():
    N = int(input())
    ans = 0.0
    P = [i for i in range(N)]
    C = [list(map(int, input().split())) for _ in range(N)]
    for p in permutations(P):
        for i in range(N - 1):
            ans += sqrt(((C[p[i + 1]][0] - C[p[i]][0]) ** 2) + ((C[p[i + 1]][1] - C[p[i]][1]) ** 2))

    for i in range(2, N + 1):
        ans /= i

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
import  itertools
N=int(input())
XY=[]
for _ in range(N):
  x, y = map(int, input().split())
  XY.append([x,y])

D=np.zeros((N, N))
for i in range(N-1):
  xi, yi=XY[i][0], XY[i][1]
  for j in range(i+1, N):
    xj, yj=XY[j][0], XY[j][1]
    distance=np.sqrt((xi-xj)**2 + (yi-yj)**2)
    D[i][j]=distance
    D[j][i]=distance

ans=0
for l in itertools.permutations(range(N)):
  dis=0
  for i in range(N-1):
    dis+=D[l[i]][l[i+1]]
  ans+=dis
print(ans/np.math.factorial(N))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(500000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def calc(p, P):
    ans = 0
    for i in range(1, len(p)):
        x1, y1 = P[p[i - 1]]
        x2, y2 = P[p[i]]
        ans += sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)

    return ans


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

    ans = 0
    num = 0
    for p in permutations(range(N)):
        ans += calc(p, P)
        num += 1
    print(ans / num)


def main():
    solve()


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import math

N = int(input())
L = [list(map(int,input().split())) for n in range(N)]
I = list(itertools.permutations(L))
sum = 0

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
from itertools import permutations
from math import factorial
def main():
    n = int(input())
    xy = [tuple(map(int, input().split())) for _ in range(n)]

    # 町同士の距離をxydisにいれる
    xydis = [[0] * n for _ in range(n)]
    for i1 in range(n):
        for i2 in range(n):
            xydis[i1][i2] = ((xy[i1][0] - xy[i2][0])**2 + (xy[i1][1] - xy[i2][1])**2)**0.5
    # 組み合わせごとの距離をdis_sumに足す。
    per = tuple(permutations(range(n), n))
    dis_sum = 0
    for pere in per:
        for j1 in range(n - 1):
            dis_sum += xydis[pere[j1]][pere[j1 + 1]]
    ans = dis_sum / factorial(n)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

lst2 = list(itertools.combinations(lst1, 2))
p = math.factorial(N) * (N - 1)
c = len(list(itertools.combinations(lst1, 2)))
total = 0

for i in lst2:
    d = ((i[1][0] - i[0][0]) ** 2 + (i[1][1] - i[0][1]) ** 2) ** 0.5
    total += d
    
num = int(p/c)
fct = math.factorial(N)

print(total * num / fct)

Submission status: Accepted

Solution code:
import itertools
import math
n = int(input())
l = [list(map(int,input().split())) for _ in range(n)]
size = math.factorial(n)
a = list(itertools.permutations(l,n))
total = 0
for i in range(size):
    for j in range(n-1):
        x1 = a[i][j][0]
        x2 = a[i][j+1][0]
        y1 = a[i][j][1]
        y2 = a[i][j+1][1]
        x_total = (x1-x2)**2
        y_total = (y1-y2)**2
        total += (x_total + y_total)**.5
print(total/size)

Submission status: Accepted

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

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

size = factorization(n)
a = list(itertools.permutations(l,n))
total = 0
for i in range(size):
    for j in range(n-1):
        x1 = a[i][j][0]
        x2 = a[i][j+1][0]
        y1 = a[i][j][1]
        y2 = a[i][j+1][1]
        x_total = (x1-x2)**2
        y_total = (y1-y2)**2
        total += (x_total + y_total)**.5
print(total/size)

Submission status: Accepted

Solution code:
import itertools

n = int(input())
town = [list(map(int, input().split())) for _ in range(n)]
x = 1
for i in range(1, n+1):
    x *= i
l = []
for j in range(n):
    l.append(j)
ans = 0
for a in itertools.permutations(l, n):
    newl = a
    length = 0
    for b in range(n-1):
        length += ((town[newl[b]][0] - town[newl[b+1]][0])**2 + (town[newl[b]][1] - town[newl[b+1]][1])**2)**(1/2) 
    ans += length
print(ans/x)

Submission status: Accepted

Solution code:
import math


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

for i in range(n):
  x, y = t[i]
  for j in range(i, n):
    x1, y1 = t[j]
    ans += math.sqrt((x-x1)**2 + (y-y1)**2)*(n-1)*2
print(ans/((n-1)*n))

Submission status: Accepted

Solution code:
from itertools import permutations
import math
n = int(input())
x,y = [],[]
for _ in range(n):
    x_, y_ =map(int,input().split())
    x.append(x_)
    y.append(y_)
c = list(permutations([i for i in range(1,n+1)],n))
sum = 0
for ci in (c):
    tmp = 0
    for i in range(len(ci)-1):
            tmp += math.sqrt((x[ci[i]-1]-x[ci[i+1]-1])**2 
                             + (y[ci[i]-1]-y[ci[i+1]-1])**2)
    sum += tmp
print(sum/len(c))

Submission status: Accepted

Solution code:
from itertools import permutations
import math
n = int(input())
x,y = [],[]
for _ in range(n):
    x_, y_ =map(int,input().split())
    x.append(x_)
    y.append(y_)

c = list(permutations([i for i in range(1,n+1)],n))

g = [[-1]*(n+1) for _ in range(n+1)]
sum = 0
for ci in (c):
    tmp = 0
    for i in range(len(ci)-1):
        if g[ci[i]][ci[i+1]] == -1:
            tmp += math.sqrt((x[ci[i]-1]-x[ci[i+1]-1])**2 
                             + (y[ci[i]-1]-y[ci[i+1]-1])**2)
        else:
            tmp += g[ci[i]][ci[i+1]]
    sum += tmp
print(sum/len(c))

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

cnt = 0
total = 0
for v in itertools.permutations(L):
    for i in range(N-1):
        x_1 = v[i][0]
        y_1 = v[i][1]
        x_2 = v[i+1][0]
        y_2 = v[i+1][1]
        total += ((x_2 - x_1) ** 2 + (y_2 - y_1) ** 2) ** 0.5
    cnt += 1

print(total/cnt)

Submission status: Accepted

Solution code:
import math
n = int(input())
towns = [list(map(int, input().split())) for _ in range(n)]
ans = 0
for i in range(n-1):
    x1, y1 = towns[i]
    for j in range(i+1, n):
        x2, y2 = towns[j]
        ans += math.sqrt((x1-x2)**2 + (y1-y2)**2)*(n-1)*2
print(ans/((n-1)*n))

Submission status: Accepted

Solution code:
from itertools import permutations

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

ans = 0
c = 0

for p in permutations(range(N)):
    dist = 0
    x1, y1 = XY[p[0]]
    for i in p[1:]:
        x, y = XY[i]
        dist += ((x1 - x) ** 2 + (y1 - y) ** 2) ** 0.5
    ans += dist
    c += 1

print(ans / c)

Submission status: Accepted

Solution code:
#C
N=int(input())
XY=[list(map(int,input().split())) for i in range(N)]
fact=[1 for i in range(N+1)]
for i in range(1,N+1):
  fact[i]=fact[i-1]*i

ans=0
for i in range(N):
  for j in range(i+1,N):
    x0,y0=XY[i]
    x1,y1=XY[j]
    dis=pow((x0-x1)**2+(y0-y1)**2,0.5)
    ans+=dis*fact[N-1]*2

print(ans/fact[N])

Submission status: Accepted

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

def distance(i, j):
    xi, yi = xy[i]
    xj, yj = xy[j]
    return (xi-xj)**2 + (yi-yj)**2

visited = [False] * n
ans = 0
def dfs(route, length):
    global ans
    if len(route)==n:
        ans += length
        return
    else:
        for i in range(n):
            if visited[i]: continue
            next_distance = distance(route[-1], i)**0.5
            visited[i] = True
            dfs(route+[i], length+next_distance)
            visited[i] = False

cnt = 1
for i in range(n):
    cnt*=i+1
    visited[i] = True
    dfs([i], 0)
    visited[i] = False
print(ans/cnt)

Submission status: Accepted

Solution code:
import math

n = int(input())
towns = [list(map(int, input().split())) for _ in range(n)]
ans = 0
c = 0
for i in range(n-1):
    x1, y1 = towns[i]
    for j in range(i+1, n):
        x2, y2 = towns[j]
        ans += math.sqrt((x1-x2)**2 + (y1-y2)**2)*(n-1)*2

print(ans/((n-1)*n))

Submission status: Accepted

Solution code:
N = int(input())
cities = []
for n in range(N):
  cities.append(tuple(map(int, input().split())))

import math
def distance(i, j):
  xi,yi = cities[i]
  xj,yj = cities[j]
  xd,yd = xi - xj, yi - yj
  return math.sqrt(xd * xd + yd * yd)

# path: これまでに通過した街の番号
def search(path):
  total = 0
  count = 0
  for i in range(N):
    if i not in path:
      count += 1
      path.append(i)
      total += (0 if len(path) == 1 else distance(i, path[-2])) + search(path)
      path.remove(i)
  if count == 0:
    return 0
  else:
    return total / count

print(search([]))

Submission status: Accepted

Solution code:
import math

N = int(input())
xy = [list(map(int,input().split())) for i in range(N)]
ave = 0
cnt = 0
import itertools
for v in itertools.permutations([int(x) for x in range(N)],N) :
    for i in range(1,len(v)) :
        ave += math.sqrt((xy[v[i-1]][0]-xy[v[i]][0])**2+(xy[v[i-1]][1]-xy[v[i]][1])**2)
    cnt += 1

ave = ave / cnt
print(ave)

Submission status: Accepted

Solution code:
def func(n):
    if n==1:
        return 1
    return n*func(n-1)
n=int(input())
L=[0 for i in range(n)]
for i in range(n):
    L[i]=list(map(int,input().split()))
ans=0
for i in range(n):
    for j in range(i+1,n):
        length=(L[i][0]-L[j][0])**2+(L[i][1]-L[j][1])**2
        length=length**0.5
        ans+=length*func(n-1)*2
print(ans/func(n))

Submission status: Accepted

Solution code:
import itertools
n = int(input())
a = [list(map(int, input().split(" "))) for i in range(n)]
ans = 0
for [ix,iy], [jx, jy] in itertools.combinations(a, 2):
  ans += ((jx-ix)**2+(jy-iy)**2)**0.5*2
print(ans/n)

Submission status: Accepted

Solution code:
import itertools
import math

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

total_length = 0
k = 0
for pattern in itertools.permutations(p):
    k += 1
    length = 0
    for i in range(N-1):
        length += math.sqrt((pattern[i+1][0] - pattern[i][0])**2 + (pattern[i+1][1] - pattern[i][1])**2)
    total_length += length

print(total_length/k)

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(N):
    for j in range(N):
        if i != j:
            result += math.sqrt((xy[i][0] - xy[j][0])**2 + (xy[i][1] - xy[j][1])**2)

print(result / N)

Submission status: Accepted

Solution code:
def II(): return int(input())
def LII(): return list(map(int, input().split()))

n=II()
town=[LII() for _ in range(n)]

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

print(distance*2/n)

Submission status: Accepted

Solution code:
import math, itertools
n = int(input())
X = list(list(map(int,input().split())) for _ in range(n))
L = list(itertools.permutations(range(n),n))
ans = 0

for l in L:
  dist = 0
  for i in range(n-1):
    s,t = l[i],l[i+1]
    vx = X[s][0] - X[t][0]
    vy = X[s][1] - X[t][1]
    dist += math.sqrt(vx**2 + vy**2)
  ans += dist

print(ans/len(L))

Submission status: Accepted

Solution code:
import itertools
import math

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

distance = []
visitedPath = list(itertools.permutations(path))
for vp in visitedPath:
  routeDistance = 0
  for i in range(len(vp)-1):
    routeDistance += math.sqrt((vp[i][0]-vp[i+1][0])**2 + (vp[i][1]-vp[i+1][1])**2)
  distance.append(routeDistance)
print(sum(distance)/len(distance))

Submission status: Accepted

Solution code:

import sys, itertools


def solve(N: int, x: "List[int]", y: "List[int]"):
    route = list(itertools.permutations([i for i in range(N)]))
    length = 0
    itter = range(N-1)
    for i in route:
        for j in itter:
            length += ((x[i[j]]-x[i[j+1]])**2+(y[i[j]]-y[i[j+1]])**2)**0.5
    print(length/len(route))
    return
    
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:
from itertools import permutations
import math
n = int(input())
x = []
y = []
for i in range(n):
    xi, yi = map(int, input().split(' '))
    x.append(xi)
    y.append(yi)

l = [i for i in range(n)]
route = list(permutations(l))
length = 0
for ls in route:
    for i in range(n-1):
        length += math.sqrt((x[ls[i+1]]-x[ls[i]])**2+(y[ls[i+1]]-y[ls[i]])**2)
ans = length/math.factorial(n)
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math

n = int(input())
xy = [list(map(int,input().split())) for i in range(n)]
q = list(itertools.permutations(range(n)))
m = len(q)

k_sum = 0

for i in range(m):
  for j in range(n-1):
    a = xy[q[i][j]][0] - xy[q[i][j+1]][0]
    x = a**2
    b = xy[q[i][j]][1] - xy[q[i][j+1]][1]
    y = b**2
    k_sum += math.sqrt(x+y)
    
print(k_sum/m)

Submission status: Accepted

Solution code:
import itertools
import math
N = int(input())
ls, val = [], 0
perm = itertools.permutations(range(N))
for i in range(N):
    x, y = map(int, input().split(' '))
    ls.append([x, y])
for i in perm:
    for j in range(N - 1):
        val += math.sqrt((ls[i[j + 1]][0] - ls[i[j]][0]) ** 2 + (ls[i[j + 1]][1] - ls[i[j]][1]) ** 2)
print(val / math.factorial(N))

Submission status: Accepted

Solution code:
import itertools

N=int(input())
xy=[list(map(int, input().split())) for _ in range(N)]
xy_d=[[0]*N for _ in range(N)]
xylist=list(itertools.permutations([n for n in range(N)],N))

for i in range(N-1):
	for h in range(i+1,N):
		xy_d[i][h]=((xy[i][0]-xy[h][0])**2+(xy[i][1]-xy[h][1])**2)**.5
		xy_d[h][i]=((xy[i][0]-xy[h][0])**2+(xy[i][1]-xy[h][1])**2)**.5

ans=0

#print(xy_d)

for g in range(len(xylist)):
	for t in range(N-1):
		#print(xy_d[xylist[g][t]][xylist[g][t+1]])
		ans+=xy_d[xylist[g][t]][xylist[g][t+1]]

print(ans/len(xylist))

Submission status: Accepted

Solution code:
import math
from itertools import permutations
N=int(input())
XYlist=[]
indexlist=[i for i in range(N)]
for _ in range(N):
    XYlist.append(tuple(map(int,input().split())))
ans=0
num=0
for indexes in permutations(indexlist,N):
    for i in range(N-1):
        ans+=math.sqrt((XYlist[indexes[i]][0]-XYlist[indexes[i+1]][0])**2+
                       (XYlist[indexes[i]][1]-XYlist[indexes[i+1]][1])**2)
    num+=1
print(ans/num)

Submission status: Accepted

Solution code:
from itertools import permutations
N = int(input())
map_xy = []
for i in range(N):
  map_xy.append(list(map(int,input().split())))
  
def length_calc(start,goal):
  #print("S&G",start,goal)
  #print(start[0],start[1],goal[0],goal[1])
  return ((goal[1]-start[1])**2 + (goal[0]-start[0])**2)**0.5
  
#########################
list=[_ for _ in range(N)]
per=permutations(list,N)


route_distance = 0
per_count = 0
for i in per:
  go_to_tuple = i
  for j in range(len(go_to_tuple)-1):
    start = map_xy[go_to_tuple[j]]
    goal = map_xy[go_to_tuple[j+1]]
    #print("LEMNGTH",length_calc(start,goal))
    route_distance += length_calc(start,goal)
  per_count += 1

#print(per_count)
ans = route_distance /  per_count
print(ans)

Submission status: Accepted

Solution code:
import math
from itertools import permutations


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

N = int(input())

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

mtx = [0 for i in range(N)] * N

mtx = [[calc_distance(a, b) for a in city] for b in city]


all_distance = 0
paths = permutations([i for i in range(N)])
cnt = 0
for pt in paths:
    distance = 0
    for idx in range(1, len(pt)):
       distance += mtx[pt[idx]][pt[idx-1]]

    all_distance += distance
    cnt += 1

all_distance /= cnt


print(all_distance)

Submission status: Accepted

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


l = [i for i in range(N)]
ans = 0
cnt = 0
for i in itertools.permutations(l, N):
    cnt += 1
    for j in range(1, N):
        x1 = x[i[j]]
        x2 = x[i[j-1]]
        y1 = y[i[j]]
        y2 = y[i[j-1]]
        ans += pow((x1 - x2)**2 + (y1 - y2)**2, 0.5)
        # print(i, j, x1, y1, x2, y2)
ans /= cnt
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math

N = int(input())
x_list = [0] * N
y_list = [0] * N
for i in range(N):
    x_list[i], y_list[i] = map(int, input().split())
l_sum = 0
l = 0
for comb in itertools.combinations(range(N), 2):
    l = (
        (x_list[comb[0]] - x_list[comb[1]]) ** 2
        + (y_list[comb[0]] - y_list[comb[1]]) ** 2
    ) ** 0.5
    l_sum += l
ans = 2 * l_sum / N
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math
N = int(input())
xy = [map(int, input().split()) for _ in range(N)]
x, y = [list(i) for i in zip(*xy)]
l=[]
for i in range(0,N):
    l.append(i)
p=list(itertools.permutations(l,N))
z=0
for j in range(0,len(p)):
    for k in range(0,N-1):
        z=z+math.sqrt(pow(x[p[j][k]]-x[p[j][k+1]],2)+pow(y[p[j][k]]-y[p[j][k+1]],2))
ans=z/len(p)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

# mod = 1
# for n in range(N, 0, -1):
#     mod *= n

g = {}
for idx in range(N):
    x, y = map(int,input().split())
    g[idx] = (x, y)

ans = []
def dfs(curr, d):
    if len(seen) == N:
        ans.append(d)
        return
    
    for i in range(N):
        if i not in seen:
            seen.add(i)
            dis = ((g[curr][0] - g[i][0])**2 + (g[curr][1] - g[i][1])**2)**(1/2)
            dfs(i, d + dis)
            seen.discard(i)
    return    

for i in range(N):
    seen = set([i])
    dfs(i, 0)

ret = 0
for a in ans:
    ret += a
print(ret / len(ans))

Submission status: Accepted

Solution code:
N = int(input())
locs = []
S = 0

for _ in range(N):
  locs.append(list(map(int,input().split())))
  
for i in range(N):
  for j in range(i+1,N):
    dis = ((locs[i][0]-locs[j][0])**2 + (locs[i][1]-locs[j][1])**2)**(1/2)
    S += dis

print(2*S/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])
  
ans=0
for i in range(n):
  for j in range(n):
    ans+=math.factorial(n-1)*math.sqrt((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)
    
print(ans/math.factorial(n))

Submission status: Accepted

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

import math

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


def calc(path):
    r = 0
    for i in range(len(path) - 1):
        p1 = P[path[i-1]]
        p2 = P[path[i]]
        dx = p1[0] - p2[0]
        dy = p1[1] - p2[1]
        r += math.sqrt(dx*dx + dy*dy)
    return r

ret = 0
numret = 0
def rec(path, rest):
    if not rest:
        global ret
        global numret
        ret += calc(path)
        numret += 1
        return
    for i in range(len(rest)):
        rec(path + [rest[i]],  rest[:i] + rest[i+1:])

rec([], [i for i in range(N)])
print(ret/numret)

Submission status: Accepted

Solution code:
import itertools
import math

def calc_dist(pos1, pos2):
    x1,y1=pos1
    x2,y2=pos2
    return math.sqrt(pow(x1-x2, 2)+pow(y1-y2, 2))

N=int(input())

distance_mat = [[-1000 for _ in range(N)] for _ in range(N)]
pos = []
for _ in range(N):
    pos.append(list(map(int, input().split())))

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

result=[]
for perm in perms:
    dist_sum = 0
    for i in range(1, N):
        source = perm[i-1]
        sink = perm[i]
        if distance_mat[source][sink]==-1000:
            dist = calc_dist(pos[source], pos[sink])
            distance_mat[source][sink] = dist
            distance_mat[sink][source] = dist
        else:
            dist = distance_mat[source][sink]
        dist_sum+=dist
    result.append(dist_sum)

import numpy as np
print(np.average(result))