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:
N=int(input())
x=[]
y=[]
for _ in range(N):
  a, b=map(int, input().split())
  x.append(a)
  y.append(b)

from math import factorial
from math import sqrt
ans=0

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

num=factorial(N-1)*2
for i in range(N-1):
  for j in range(i+1,N):
    ans+=num*d(x[i],x[j],y[i],y[j])
print(ans/factorial(N))

Submission status: Accepted

Solution code:
from itertools import permutations
N = int(input())
position = []
for p in range(N):
    position.append(list(map(int,input().split())))

D = [[0]*N for _ in range(N)]
for i in range(N):
    for j in range(i+1,N):
        dist=(position[i][0]-position[j][0])**2
        dist+=(position[i][1]-position[j][1])**2
        dist=dist**(1/2)
        D[i][j] = dist
        D[j][i] = dist

dist=[]
for p in permutations(range(N),N):
    dist_temp=0
    for p_idx in range(1,len(p)):
        p_start = p[p_idx-1]
        p_end = p[p_idx]
        dist_temp+=D[p_start][p_end]
    dist.append(dist_temp)
        
print(sum(dist)/len(dist))

Submission status: Accepted

Solution code:
import itertools
import math
N = int(input())
XY = [list(map(int,input().split())) for i in range(N)]
L = 0#経路長の和
for i in list(itertools.permutations(XY)):#順列に対し
    distance = 0
    for n in range(N-1):#経路長を求める
        distance += math.sqrt((i[n+1][0]-i[n][0])**2 + (i[n+1][1]-i[n][1])**2)
    L += distance
print(L/math.factorial(N))

Submission status: Accepted

Solution code:
import itertools

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

def fact(n):
    ans=1
    for i in range(n):
        ans*=(i+1)
    return ans

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

ls=list(itertools.permutations(range(n)))
ans=0
for l in ls:
   for i in range(n-1):
       ans+=dist(d[l[i]][0],d[l[i]][1],d[l[i+1]][0],d[l[i+1]][1])
ans/=fact(n)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
n= int(input())
ls = []
for i in range(n):
    a = list(map(int,input().split()))
    ls.append(a)
ans = []
for i in permutations(ls,n):
    #print(i)
    result = 0
    for j in range(n-1):
        result += (((i[j][0]-i[j+1][0])**2+(i[j][1]-i[j+1][1])**2)**(1/2))
    ans.append(result)

ans = (1/len(ans))*sum(ans)
print(ans)

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    sm = 0
    pl = []
    for i in range(n):
        x,y = map(int,ipt().split())
        pl.append((x,y))
    nm = 0
    for i in range(n):
        xi,yi = pl[i]
        for j in range(i+1,n):
            xj,yj = pl[j]
            sm += math.sqrt((xj-xi)**2+(yj-yi)**2)
            nm += 1
    print(sm/nm*(n-1))



    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N = I()
xy = [LI() for i in range(N)]

sum = 0  # 2点間の距離の総和*2
for i in range(N):
    for j in range(N):
        sum += ((xy[i][0]-xy[j][0])**2 + (xy[i][1]-xy[j][1])**2)**.5

print(sum/N)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

lst = np.arange(1,N+1)
perm = list(itertools.permutations(lst))

ans = 0
lenperm = len(perm)
for k in range(lenperm):
  for p in range(N-1):
    x1 = x[perm[k][p+1]-1]
    y1 = y[perm[k][p+1]-1]
    x0 = x[perm[k][p]-1]
    y0 = y[perm[k][p]-1]
    tans = np.sqrt((x1-x0)**2 + (y1-y0)**2)
    ans += tans

print(ans / lenperm)

Submission status: Accepted

Solution code:
import numpy as np
def factorial(n):
  if (n==1):
    return 1
  return n*factorial(n-1)

n = int(input())
x = []
y = []
for i in range(n):
  x_, y_ = list(map(int, input().split()))
  x.append(x_)
  y.append(y_)
val = 0
for i in range(n):
  for j in range(i+1, n):
    val += np.sqrt((x[i] - x[j])**2 + (y[i] - y[j])**2)

ans = val/factorial(n) * factorial(n-1) * 2
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
xy = [list(map(int, input().split())) for i in range(N)]
 
from itertools import permutations
from math import sqrt
 
paths = list(permutations(range(N), N))
l = len(paths)
total = 0
for path in paths:
    tmp = 0
    x, y = xy[path[0]][0], xy[path[0]][1]
    for p in path[1:]:
        px, py = xy[p][0], xy[p][1]
        tmp += sqrt((px-x)**2 + (py-y)**2)
    total += tmp
print(total / l)

Submission status: Accepted

Solution code:
n=int(input())
c=[[*map(int,input().split())] for _ in range(n)]
print(sum(((x-z)**2+(y-w)**2)**0.5 for x,y in c for z,w in c)/n)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import permutations
N = int(input())
ls = []
for i in range(N):
    ls.append([int(j) for j in input().split()])
arr = list(range(N))
ans = 0
num = 0
for x in permutations(arr, N):
    num += 1
    for y, z in zip(x, x[1:]):
        ans += ((ls[y][0] - ls[z][0])**2 + (ls[y][1] - ls[z][1])**2)**(1/2)
print(ans/num)

Submission status: Accepted

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

from itertools import permutations
from math import sqrt

paths = list(permutations(range(N), N))
l = len(paths)
total = 0
for path in paths:
    tmp = 0
    x, y = xy[path[0]][0], xy[path[0]][1]
    for p in path[1:]:
        px, py = xy[p][0], xy[p][1]
        tmp += sqrt((px-x)**2 + (py-y)**2)
    total += tmp
print(total / l)

Submission status: Accepted

Solution code:
n=int(input())
l=[]
for _ in range(n):
  l.append(list(map(int, input().split())))
#print(l)
import itertools
d=len(list(itertools.permutations(l)))
cnt=0
fin=0
for v in itertools.permutations(l):
  chk=0
  for z in range(len(v)-1):
    chk+=((v[z][0]-v[z+1][0])**2+(v[z][1]-v[z+1][1])**2)**0.5
  fin+=chk
print(fin/d)

Submission status: Accepted

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

def factorial(n):
    if n == 0:
        return 1
    else:
        a = 1
        for i in range(n):
            a *= n - i
        return a

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

suml = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        suml += distance(xy[i], xy[j])

ave = (suml * 2 * factorial(n - 1)) / factorial(n)
print(ave)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
Cord = np.zeros((N,2),dtype=int)
for T in range(0,N):
    Cord[T] = np.array([int(x) for x in input().split()])
Dist = 0
for T in range(0,N):
    for TT in range(T+1,N):
        Dist += np.linalg.norm(Cord[T,:]-Cord[TT,:])
print(Dist*2/N)

Submission status: Accepted

Solution code:
N = int(input())
pos = [list(map(int, input().split(" "))) for i in range(N)]
ans=0
for i in range(N):
  for j in range(N):
    x_dist = (pos[i][0]-pos[j][0])**2
    y_dist = (pos[i][1]-pos[j][1])**2
    dist = (x_dist+y_dist)**0.5
    ans+=dist
print(ans/N)

Submission status: Accepted

Solution code:
from itertools import permutations as perm
n = int(input())
cities = [list(map(int, input().split())) for _ in range(n)]
perms = list(range(n))
res=[]
for p in perm(perms):
    tmp=0
    for i in range(1,n):
       tmp+=((cities[p[i]][0]-cities[p[i-1]][0])**2+(cities[p[i]][1]-cities[p[i-1]][1])**2)**(1/2)
    res.append(tmp)
print(sum(res)/len(res))

Submission status: Accepted

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

import itertools
perm = list(itertools.permutations(range(n)))
d = 0
for v in perm:
  lx,ly = p[v[0]]
  for v2 in v[1:]:
    x,y=p[v2]
    d += ((x-lx)**2+(y-ly)**2)**0.5
print(d/len(perm))

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

import math
def calc():
    total = 0
    for i in range(1, N):
        x1, y1 = towns[i]
        x2, y2 = towns[i - 1]
        l = math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
        total += l
    return total

ans = 0
def g(n):
    global ans
    if n == N:
        ans += calc()
        return
    for i in range(n, N):
        towns[i], towns[n] = towns[n], towns[i]
        g(n + 1)
        towns[i], towns[n] = towns[n], towns[i]

g(0)
print(ans / f(N))

Submission status: Accepted

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

from fractions import gcd
# from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement
import math

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

ret = 0
coms = permutations(range(N), N)

ct = 0
for com in coms:
    pt = pos[com[0]]
    for i in com[1:]:
        n = pos[i]
        ret += math.sqrt((pt[0]-n[0])**2 + (pt[1] - n[1])**2)
        pt = n
    ct += 1

print(ret / ct)

Submission status: Accepted

Solution code:
import itertools
import math

n=int(input())
town=[]
for i in range(n):
    town.append([int(i) for i in input().split()])

dist_sum=0
for per in itertools.permutations(town,n):
    for i in range(n-1):
        dist_sum += math.sqrt((per[i][0]-per[i+1][0])**2+(per[i][1]-per[i+1][1])**2)
print(dist_sum/math.factorial(n))

Submission status: Accepted

Solution code:
from itertools import permutations
n=int(input())
x=list(permutations([list(map(int,input().split())) for _ in range(n)]))
c=0.0
for i in x:
  a=i[0][0]
  b=i[0][1]
  for j in i[1:]:
    c+=((j[0]-a)**2+(j[1]-b)**2)**.5
    a=j[0]
    b=j[1]
print(c/len(x))

Submission status: Accepted

Solution code:
import math
from itertools import permutations


def main():
    n = int(input())
    xy = [tuple(map(int, input().split())) for _ in range(n)]

    dist = []
    for i in range(n):
        d = []
        for j in range(n):
            if i == j:
                d.append(0.0)
                continue
            x1, y1 = xy[i]
            x2, y2 = xy[j]
            d.append(math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2))
        dist.append(d)

    avg = 0
    perms = list(permutations(range(n)))
    for i in perms:
        d = 0
        for j in range(n)[:-1]:
            d += dist[i[j]][i[j + 1]]
        avg += d / len(perms)
    print(avg)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
import itertools

N = int(input())
x, y = [], []
for _ in range(N):
  a, b = map(int, input().split())
  x.append(a)
  y.append(b)
  
ans = 0
for r in itertools.permutations([i for i in range(N)]):
  for i in range(1, N):
    ans += math.sqrt((x[r[i]]-x[r[i-1]])**2 + (y[r[i]]-y[r[i-1]])**2)
ans /= math.factorial(N)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
import math

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

# 2点間の距離
def length(x1,y1,x2,y2):
    return(math.sqrt(abs(x2-x1)**2+abs(y2-y1)**2))

point = 0

for i in permutations(li):
    for j in range(1,n):
        point += length(i[j-1][0],i[j-1][1],i[j][0],i[j][1])

print(point/math.factorial(n))

Submission status: Accepted

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

for x1,y1 in xy:
    for x2,y2 in xy:
        X = x1-x2
        Y = y1-y2
        ans += (X**2+Y**2)**0.5

print(ans/n)

Submission status: Accepted

Solution code:
from math import factorial

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

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

print(cnt * 2 * factorial(N - 1) / factorial(N))

Submission status: Accepted

Solution code:
import sys
import itertools
import math
input = lambda: sys.stdin.readline().rstrip()

def main():
    n = int(input())
    loc = [list(map(int,input().split())) for _ in range(n)]
    arr = list(itertools.permutations(loc))
    p = math.factorial(n)
    dis = 0
    for i in range(p):
        for j in range(n-1):
            dis += math.sqrt((arr[i][j+1][1]-arr[i][j][1])**2+(arr[i][j+1][0]-arr[i][j][0])**2)
    print(dis/p)
    
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import math
N = int(input())
XY = [list(map(int,input().split())) for _ in range(N)]
P = list(itertools.permutations(XY))
L = []
for p in P:
    length = 0
    for i in range(1,N):
        length += math.sqrt((p[i][0]-p[i-1][0])**2+(p[i][1]-p[i-1][1])**2)
    L.append(length)
print(sum(L)/len(P))

Submission status: Accepted

Solution code:
import itertools
import math
from statistics import mean

N = int(input())
towns = []
for i in range(N):
    xi,yi=map(int,input().split())
    towns.append([xi,yi])
order=[int(x) for x in range(N)]
root_time=[]
for one_order in itertools.permutations(order):
    root_t=0
    for i in range(len(one_order)-1):
        root_t += math.sqrt((towns[one_order[i]][0]-towns[one_order[i+1]][0])**2+(towns[one_order[i]][1]-towns[one_order[i+1]][1])**2)
    root_time.append(root_t)

print(mean(root_time))

Submission status: Accepted

Solution code:
#145c Average length
#順列探索の勉強
import itertools
import math
n=int(input())
data=[]
for i in range(n):
  point=list(map(int,input().split()))
  data.append(point)
length=0
lis=[ x for x in range(n) ]
permutation=itertools.permutations(lis)
ansbig=0
for one_case in permutation:
  alldistance=0
  for k in range(n-1) :
    xk=data[one_case[k]][0]
    yk=data[one_case[k]][1]
    xknext=data[one_case[k+1]][0]
    yknext=data[one_case[k+1]][1]
    distance=((xk-xknext)**2+(yk-yknext)**2)**(1/2)
    alldistance+=distance
  ansbig+=alldistance
  
print(ansbig/math.factorial(n))

Submission status: Accepted

Solution code:
# 15
# ABC145 C Average Length

import itertools
import math

n = int(input())
xy_l = [[int(x) for x in input().split()] for y in range(n)]

per = itertools.permutations(list(range(n)))
num = math.factorial(n)
ans = 0
for order in per:
    _sum = 0
    for i in range(n-1):
        _sum += ((xy_l[order[i]][0] - xy_l[order[i+1]][0])**2
                 + (xy_l[order[i]][1] - xy_l[order[i+1]][1])**2)**0.5
    ans += _sum
print(ans/num)

Submission status: Accepted

Solution code:
from itertools import permutations
N=int(input())
town=[]
for i in range(N):
    x,y=map(int,input().split())
    town.append((x,y))

ans=0
for i,j in permutations(town,2):
    ans+=(((i[0]-j[0])**2+(i[1]-j[1])**2)**0.5)
print(ans/N)

Submission status: Accepted

Solution code:
import itertools
import math
n = int(input())
d = {}
for i in range(n):
  d[i] = list(map(int, input().split()))

p = [i for i in range(n)]
q = list(itertools.permutations(p, n))
arr = []
for i in range(len(q)):
  dis = 0
  for j in range(1, n):
    start = d[q[i][j - 1]]
    stop = d[q[i][j]]
    dis += math.sqrt((start[0] - stop[0]) ** 2 + (start[1] - stop[1]) ** 2)
  arr.append(dis)
ans = sum(arr) / len(q)
print(ans)

Submission status: Accepted

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

ans = 0
for p in itertools.permutations([i for i in range(N)]):
    for i,v in enumerate(p):
        x,y = position[v]
        if i == 0:
            nowx = x
            nowy = y
        else:
            ans += ((x-nowx)**2+(y-nowy)**2)**0.5
            nowx = x
            nowy = y

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

print(ans/pattern)

Submission status: Accepted

Solution code:
from math import sqrt
n=int(input())
x=[]
y=[]
for _ in range(n):
  a,b=map(int,input().split())
  x.append(a)
  y.append(b)

dist=0

for i in range(n-1):
  for j in range(i+1,n):
    d=(x[i]-x[j])**2+(y[i]-y[j])**2
    dist+=sqrt(d)
print(dist*2/n)

Submission status: Accepted

Solution code:
from itertools import permutations
N = int(input())
point = []
dist_sum = 0
per = 0

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

for p in permutations(point, N):
    for i in range(N - 1):
        dist_sum += ((p[i][0] - p[i + 1][0])**2 + (p[i][1] - p[i + 1][1])**2)**0.5
    per += 1

print(dist_sum / per)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import math
import itertools


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


if __name__ == "__main__":
    N = int(input())

    towns = []
    for _ in range(N):
        x, y = [int(x) for x in input().split(" ")]
        towns.append((x, y))
    dists = []
    for route in itertools.permutations(range(N)):

        d = 0
        for i in range(N - 1):
            from_ = route[i]
            to = route[i + 1]
            d += dist(towns[from_], towns[to])
        dists.append(d)
    print(sum(dists) / len(dists))

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt

def readinput():
    n=int(input())
    xyList=[]
    for _ in range(n):
        x,y=list(map(int,input().split()))
        xyList.append((x,y))
    return n,xyList

def main(n,xyList):
    sum=0.0
    factn=0
    for tup in permutations(range(n)):
        #print(tup)
        factn+=1
        x0=xyList[tup[0]][0]
        y0=xyList[tup[0]][1]
        for i in tup:
            x=xyList[i][0]
            y=xyList[i][1]
            sum+=sqrt((x-x0)**2+(y-y0)**2)
            x0=x
            y0=y
    ans=sum/factn
    return ans

if __name__=='__main__':
    n,xyList=readinput()
    #print(xyList)
    ans=main(n,xyList)
    print(ans)

Submission status: Accepted

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

p=list(itertools.permutations(lis,n))
#print(plot)
#print(plot[p[0][0]])
cnt=0
for j in range(len(p)):
    dis=0
    for k in range(n-1):
        dis+=((plot[p[j][k+1]][1]-plot[p[j][k]][1])**2+(plot[p[j][k+1]][0]-plot[p[j][k]][0])**2)**.5
    cnt+=dis
    #print(dis)
print(cnt/len(p))

Submission status: Accepted

Solution code:
import itertools
import math
N = int(input())
x_y = {i : list(map(int, input().split())) for i in range(N)}
P = list(itertools.permutations(range(N)))
tmp = 0
for p in P:
    for n in range(N-1):
        #print(tmp)
        tmp += math.sqrt((x_y[p[n]][0] - x_y[p[n+1]][0])**2 + (x_y[p[n]][1] - x_y[p[n+1]][1])**2)

print(tmp/len(P))

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt
n = int(input())
town = []
for i in range(n):
    town_i = list(map(int,input().split()))
    town.append(town_i)

cnt = 0
length = 0
for j in permutations(range(n)):
    x,y = town[j[0]][0],town[j[0]][1]
    for k in range(1,n):
        length += sqrt((x-town[j[k]][0])**2+(y-town[j[k]][1])**2)
        x = town[j[k]][0]
        y = town[j[k]][1]
    cnt += 1

print(length/cnt)

Submission status: Accepted

Solution code:
import itertools
N = int(input())
coordinate = []
order = []
total = 0
count = 0

for i in range(N):
    order.append(i)
    coordinate.append(list(map(float,input().split())))

#print(coordinate)

for vect in itertools.permutations(order):
    #print(vect)
    count+=1
    individual = 0.0
    for i in range(1,N):
        individual += ((coordinate[vect[i]][0]-coordinate[vect[i-1]][0])**2+(coordinate[vect[i]][1] - coordinate[vect[i-1]][1])**2)**0.5
    total +=individual

print(total/count)

Submission status: Accepted

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

N=[x for x in range(n)]

p_list = itertools.permutations(N)
n_num=math.factorial(n)

ans = 0
for i in p_list:
    step = 0
    j_prev = 0
    len = 0
    for j in i:
        if step == 0:
            j_prev=j
            step = 1
            continue
        len += math.sqrt((l[j][0]-l[j_prev][0])**2+(l[j][1]-l[j_prev][1])**2)
        j_prev=j
    ans += len/n_num
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def solve(N, X, Y):
    ret = 0
    counter = 0
    stack = deque()
    cities = [i for i in range(N)]
    for city_idx in cities:
        stack.append([0, city_idx, cities[:city_idx] + cities[city_idx + 1:]])

    while stack:
        dist, city_idx, rest = stack.pop()
        if not rest:
            ret += dist
            counter += 1

        for idx, next_city_idx in enumerate(rest):
            stack.append([dist + ((X[city_idx] - X[next_city_idx])**2 + (Y[city_idx] - Y[next_city_idx])**2)**(1/2), next_city_idx, rest[:idx] + rest[idx + 1:]])

    print(ret / counter)

if __name__ == "__main__":
    N = int(input())
    X = []
    Y = []

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

    solve(N, X, Y)

Submission status: Accepted

Solution code:
import math

n = int(input())

def distance(x1, y1, x2, y2):
    return math.sqrt((x1-x2)**2 + (y1-y2)**2)
distance_sum=0

c=[0]*n
for i in range(n):
    coordinate=list(map(int,input().split()))
    c[i]=coordinate


for i in range(n-1):
    for j in range(i+1,n):
        distance_sum+=distance(c[i][0],c[i][1],c[j][0],c[j][1])
    
distance_sum*=2
distance_sum*=(n-1)
distance_sum=distance_sum/(n*(n-1))

print(distance_sum)

Submission status: Accepted

Solution code:
import math

N = int(input())
xy = [map(int ,input().split()) for i in range(N)]
x,y = [list(i) for i in zip(*xy)]
d = 0
for i in range(N-1) :
    for j in range(i+1,N) :
        d += math.sqrt( (x[i]-x[j])**2 + (y[i] - y[j])**2 )

print(d*2/N)

Submission status: Accepted

Solution code:
import math
import itertools

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

sums = []
for li in list(itertools.permutations(range(n))):
    _sum = 0
    for i in range(n):
        if i == n - 1: continue
        dx = abs(xys[li[i]][0] - xys[li[i + 1]][0])
        dy = abs(xys[li[i]][1] - xys[li[i + 1]][1])
        _sum += math.sqrt(dx**2 + dy**2)
    sums.append(_sum)

print(sum(sums) / len(sums))

Submission status: Accepted

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

ans = []
for i in range(0,n):
  for j in range(0,n):
    k = sqrt((XY[i][0]-XY[j][0])**2 + (XY[i][1]-XY[j][1])**2)
    ans.append(k)
    
print(sum(ans)/n)

Submission status: Accepted

Solution code:
N = int(input())
X = []
Y = []
sum=0
#距離の和を計算
for _ in range(N):
  x,y=map(int,input().split())
  for i, [x_,y_] in enumerate(zip(X,Y)):
    sum+=((x-x_)**2+(y-y_)**2)**(0.5)
  X.append(x)
  Y.append(y)

print(sum*2/N)

Submission status: Accepted

Solution code:
n = int(input())
x = []
for i in range(n):
    a = list(map(int,input().split()))
    x.append(a)
#print(x)
path_length = 0
cnt = 0
import itertools
for p in itertools.permutations(x):
    #print(p, p[1:])
    cnt += 1
    for (x1,y1), (x2,y2) in zip(p, p[1:]):
        path_length += ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** .5
#print(cnt)
print(path_length/(cnt))

Submission status: Accepted

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

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

def dist(a, b):
    x1, y1 = a[0], a[1]
    x2, y2 = b[0], b[1]
    return sqrt((x1 - x2)**2 + (y1 - y2)**2)

ans = 0
for combo in permutations(range(N)):
    temp = 0
    for i in range(1, N):
        temp += dist(towns[combo[i]], towns[combo[i - 1]])
    ans += temp

print(ans / factorial(N))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline

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

import math
def dist(coord1, coord2):
    return math.sqrt((coord1[0] - coord2[0]) ** 2 + (coord1[1] - coord2[1]) ** 2)

from itertools import permutations

sum = 0
count = 0
for p in permutations(XY):
    for i in range(N-1):
        sum += dist(p[i], p[i+1])

    count += 1

print(sum / count)

Submission status: Accepted

Solution code:

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

from itertools import permutations
a = range(N)
Ps = list(permutations(a))
#print('Ps', Ps)

keiro = []
for P in Ps:
    #print('P', P)
    for i in range(N-1):
        keiro.append( ((xy[P[i]][0] - xy[P[i+1]][0])**2 + (xy[P[i]][1] - xy[P[i+1]][1])**2 )**0.5 )
out=sum(keiro)/len(Ps)
#print('keiro', keiro)
print(out)

Submission status: Accepted

Solution code:
import itertools
n = int(input())
m = []
for i in range(n):
    x,y = map(int,input().split())
    m.append((x,y))
check = list(itertools.permutations([i for i in range(n)]))
ans = 0
for i in check:
    for c,j in enumerate(i):
        if c == n-1:
            continue
        ans += ((m[j][0]-m[i[c+1]][0])**2+(m[j][1]-m[i[c+1]][1])**2)**0.5
for i in range(1,n+1):
    ans/=i
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math
n = int(input())
a = [ int(x) for x in range(1,n+1)]
jun = list(itertools.permutations(a))
xy = [map(int, input().split()) for _ in range(n)]
x, y = [list(i) for i in zip(*xy)]


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import permutations
N = int(input())
comb = list(permutations([i for i in range(0, N)], N))
xy = []
for _ in range(N):
    x, y = map(int, input().split())
    xy.append([x, y])
ans = 0
for c in comb:
    for i in range(0, N-1):
        x = ((xy[c[i]][0] - xy[c[i+1]][0]) ** 2)
        y = ((xy[c[i]][1] - xy[c[i+1]][1]) ** 2)
        ans += (x + y) ** 0.5
print(ans/len(comb))

Submission status: Accepted

Solution code:
import math
import itertools

n = int(input())
xy = [map(int, input().split()) for _ in range(n)]
x, y = [list(i) for i in zip(*xy)]
l = [i for i in range(n)]
a = float(0)

k = list(itertools.permutations(l,n))
for i in range(math.factorial(n)):   
    for j in range(n-1):
        a += (((x[k[i][j]]-x[k[i][j+1]]) ** 2) + ((y[k[i][j]]-y[k[i][j+1]]) ** 2)) ** 0.5
        
print(a/math.factorial(n))

Submission status: Accepted

Solution code:
import math
import numpy as np
from itertools import permutations

N = int(input())

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

a = []
for i in range(N):
    a.append(list(map(int, input().split())))
    
total = 0
for i in permutations(a):
    for j in range(N-1):
        total += cal(i[j][0], i[j][1], i[j+1][0], i[j+1][1])
print(total / math.factorial(N))

Submission status: Accepted

Solution code:
import numpy as np
n=int(input())
sm=0
za=[]
def dis(x,y):
  x=np.array(x)
  y=np.array(y)
  return np.linalg.norm(x-y)
for i in range(n):
  za.append(list(map(int,input().split())))

for i in range(n):
  for j in range(n):
    sm+=dis(za[i],za[j])
print(sm/n)

Submission status: Accepted

Solution code:
#why is this solotion valid?
"""
n=int(input())
xy=[]
for _ in range(n):
	x,y=map(int,input().split())
	xy.append([x,y])
ans=0
for i in range(n):
	for j in range(n):
		ans+=((xy[i][0]-xy[j][0])**2+(xy[i][1]-xy[j][1])**2)**0.5
print(ans/n)
"""



from itertools import permutations
from math import hypot, factorial

n=int(input())
a=[list(map(int,input().split()))for _ in range(n)]
d = lambda x1,y1,x2,y2: ((x1-x2)**2 + (y1-y2)**2)**0.5

x = 0
for i in permutations(a):
	for j in range(n-1):
		x += d(i[j][0],i[j][1], i[j+1][0],i[j+1][1])

#for i in range(n): f*=i+1
print(x / factorial(n))

Submission status: Accepted

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

n=int(input())
a=[list(map(int,input().split()))for _ in range(n)]
d = lambda x1,y1,x2,y2: ((x1-x2)**2 + (y1-y2)**2)**0.5

x = 0
for i in permutations(a):
	for j in range(n-1):
		x += d(i[j][0],i[j][1], i[j+1][0],i[j+1][1])

#for i in range(n): f*=i+1
print(x / factorial(n))