Problem:


Score : 300 points

Problem Statement

There are N towns in a coordinate plane. Town i is located at coordinates (x_i, y_i). The distance between Town i and Town j is \sqrt{\left(x_i-x_j\right)^2+\left(y_i-y_j\right)^2}.

There are N! possible paths to visit all of these towns once. Let the length of a path be the distance covered when we start at the first town in the path, visit the second, third, \dots, towns, and arrive at the last town (assume that we travel in a straight line from a town to another). Compute the average length of these N! paths.

Constraints

2 \leq N \leq 8

-1000 \leq x_i \leq 1000

-1000 \leq y_i \leq 1000

\left(x_i, y_i\right) \neq \left(x_j, y_j\right) (if i \neq j)

(Added 21:12 JST) All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

Print the average length of the paths.
Your output will be judges as correct when the absolute difference from the judge's output is at most 10^{-6}.

Sample Input 1

3
0 0
1 0
0 1

Sample Output 1

2.2761423749

There are six paths to visit the towns: 1 → 2 → 3, 1 → 3 → 2, 2 → 1 → 3, 2 → 3 → 1, 3 → 1 → 2, and 3 → 2 → 1.

The length of the path 1 → 2 → 3 is \sqrt{\left(0-1\right)^2+\left(0-0\right)^2} + \sqrt{\left(1-0\right)^2+\left(0-1\right)^2} = 1+\sqrt{2}.

By calculating the lengths of the other paths in this way, we see that the average length of all routes is:

\frac{\left(1+\sqrt{2}\right)+\left(1+\sqrt{2}\right)+\left(2\right)+\left(1+\sqrt{2}\right)+\left(2\right)+\left(1+\sqrt{2}\right)}{6} = 2.276142...

Sample Input 2

2
-879 981
-866 890

Sample Output 2

91.9238815543

There are two paths to visit the towns: 1 → 2 and 2 → 1. These paths have the same length.

Sample Input 3

8
-406 10
512 859
494 362
-955 -475
128 553
-986 -885
763 77
449 310

Sample Output 3

7641.9817824387



Sample input:
3
0 0
1 0
0 1


Sample output:
2.2761423749

Submission status: Accepted

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

for i in range(N-1):
  for j in range(i+1, N):
    kari=(xy[i][0]-xy[j][0])*(xy[i][0]-xy[j][0])+(xy[i][1]-xy[j][1])*(xy[i][1]-xy[j][1])
    nagasa=math.sqrt(kari)
    nagasas.append(nagasa)
wa=sum(nagasas)
n_kumiawase=N*(N-1)/2
kumiawase=math.factorial(N)
n_set=kumiawase/n_kumiawase
kotae=wa*n_set*(N-1)/kumiawase
print(kotae)

Submission status: Accepted

Solution code:
import sys
from collections import *
from heapq import *
from fractions import gcd
import itertools
import math

sys.setrecursionlimit(10**6)

def InMap(): return list(map(int, input().split(' ')))
def In(): return int(input())
def InS(): return input()

N = In()
pos = []
for i in range(N):
    pos.append(InMap())

Res = 0
for v in itertools.permutations(pos, N):
    tmp = 0
    for i in range(N - 1):
        tmp += math.sqrt((v[i][0] - v[i+1][0])**2 + (v[i][1] - v[i+1][1])**2)
    Res += tmp
print(Res / float(math.factorial(N)))
exit()

Submission status: Accepted

Solution code:

import numpy as np
import itertools as it
N = int(input())
pos = []
for n in range(N):
    pos.append(tuple([int(x) for x in input().split()]))
per = list(it.permutations(pos))

distance = 0
for p in range(len(per)):
    for n in range(len(per[p])-1):
        distance += np.sqrt((per[p][n][0]-per[p][n+1][0])**2 + (per[p][n][1]-per[p][n+1][1])**2)
distance = distance / len(per)

print(distance)

Submission status: Accepted

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

import itertools
import numpy as np
import math

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

Sum_N = 0

for i in range(len(p)):

    Sum = 0

    for j in range(N - 1):
        Sum += math.sqrt((x[p[i][j]] - x[p[i][j + 1]]) ** 2 + (y[p[i][j]] - y[p[i][j + 1]]) ** 2)

    Sum_N += Sum

print(Sum_N / len(p))

Submission status: Accepted

Solution code:
n = int(input())

edge = []
X,Y = map(int,input().split())
x = [X]
y = [Y]

for j in range(n-1):
    a,b = map(int,input().split())
    for ex,ey in zip(x,y):
        edge.append(((a-ex)**2+(b-ey)**2)**0.5)
    x.append(a)
    y.append(b)

me = sum(edge)/len(edge)
print(me*(n-1))

Submission status: Accepted

Solution code:
import math

N = int(input())
route = math.factorial(N)
town = []
d = 0.0

for i in range(N):
  town.append(list(map(int, input().split())))

for t in town:
  for tt in town:
    d += math.sqrt((tt[0]-t[0])**2 + (tt[1]-t[1])**2) * (route / N)

print(d / route)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from math import factorial, sqrt
from itertools import permutations
read = sys.stdin.read
readline = sys.stdin.readline

N = int(readline())
xy = np.array(read().split(), np.int64).reshape(N, 2)
distance = [[0.0] * N for _ in range(N)]

for i in range(N - 1):
    for j in range(i + 1, N):
        tmp = sqrt(np.sum((xy[i] - xy[j]) ** 2))
        distance[j][i] = tmp
        distance[i][j] = tmp

answer = 0
for i in permutations(range(N)):
    for j in range(N - 1):
        answer += distance[i[j]][i[j + 1]]

print(answer / factorial(N))

Submission status: Accepted

Solution code:
from itertools import permutations
import math
def rangeT(a,b):
    return (math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2 ))

n=int(input())

X=[[0]*2 for _ in range(n)]

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

total=0
for perm in permutations(range(n)):
    for i,j in zip(perm,perm[1:]):
        total += rangeT(X[i],X[j])

print(total/math.factorial(n))

Submission status: Accepted

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

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

l = [[0 for _ in range(n)] for _ in range(n)]
# print(d)
# print(l)

for i, j in combinations(range(n), 2):
    # print("comb:", i, j)
    dist = (d[i][0] - d[j][0]) ** 2 + (d[i][1] - d[j][1]) ** 2
    dist = sqrt(dist)
    # print(dist)
    # print(i, j)
    l[i][j] = dist
    l[j][i] = dist


# print(l)

s = 0
for p in permutations(range(n)):
    # print(p)
    for k in range(len(p) - 1):
        s += l[p[k]][p[k + 1]]

print(s / factorial(n))

Submission status: Accepted

Solution code:
import itertools
import math

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

patterns = list(itertools.permutations([i for i in range(n)], n))
# print(patterns)

def calc_length(i, j):
    xi, yi = i
    xj, yj = j

    return math.sqrt((xi - xj) ** 2 + (yi - yj)**2)

def calc_length_many(pattern):
    num = 0
    # print(pattern)
    for k in range(len(pattern) -1):
        i = xys[pattern[k]]
        j = xys[pattern[k+1]]
        num += calc_length(i, j)
    return num
ans = 0
# print(patterns[0])
for i in range(len(patterns)):
    # print(patterns[i])
    ans += calc_length_many(patterns[i])

print(ans / len(patterns))

Submission status: Accepted

Solution code:
from itertools import permutations
from decimal import *
import math

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

    ans = 0

    for A in permutations(X):
        tmp = 0
        i = 0
        pre_x = 0
        pre_y = 0
        for x, y in A:
            if i == 0:
                pre_x = x
                pre_y = y
                i += 1
            else:
                tmp = (x - pre_x) ** 2 + (y - pre_y) ** 2
                ans += tmp ** 0.5
                i += 1 
    
    ans = Decimal(ans) / Decimal(math.factorial(N))
    print(ans)




  

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

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

def culc(L,R):
    return math.sqrt((L[0]-R[0])**2+(L[1]-R[1])**2)

sum=0
for j in range(1,N):
    for k in range(j):
        sum+=culc(P[j],P[k])


ans=2*sum/N
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#C
import math
import itertools
n = int(input())
n_list = [x+1 for x in range(n)]
num = math.factorial(n)
n_per = list(itertools.permutations(n_list))
p_list = []
for i in range(n):
    x,y = map(int, input().split())
    p_list.append([x, y])
p_sum = 0
for keiro in n_per:
    p_min_sum = 0
    #print(keiro)
    for p_n in range(n-1):
        #print(keiro[p_n])
        #print(p_list[keiro[p_n]-1])
        p_1 = math.sqrt((p_list[keiro[p_n]-1][0] - p_list[keiro[p_n + 1] - 1][0])**2 + (p_list[keiro[p_n]-1][1] - p_list[keiro[p_n + 1] - 1][1])**2)
        p_min_sum += p_1
    p_sum += p_min_sum
print(p_sum / num)

Submission status: Accepted

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

from itertools import permutations
import math
l_sum = 0
dic={}
lx = list(range(0,N))

for k,i in enumerate(xy):
  l = []
  for j in xy:
    length = ((i[0]-j[0])**2 + (i[1]-j[1])**2)**(1/2)
    l.append(length)
    
  dic[k]=l
  
p = list(permutations(lx,N))
for i in p:
  for j in range(N-1):
    l_sum += dic[i[j]][i[j+1]]
    
print(l_sum/math.factorial(N))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    n = INT()
    lis = [LIST() for _ in range(n)]
    ans = 0
    #print(*lis)
    for i in range(n):
        for j in range(i, n):
            ans += sqrt((lis[i][0] - lis[j][0]) ** 2 + (lis[i][1] - lis[j][1]) ** 2)
    m = factorial(n)
    ans *= 2 * factorial(n-1)
    #print(ans)
    print(ans/m)

if  __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

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

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

routes=list(itertools.permutations(range(n), n))
sum=0

for i in routes:
    for j in range(n-1):
        sum+=get_distance(ls[i[j]],ls[i[j+1]])
print(sum/len(routes))

Submission status: Accepted

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

ans = 0
for i in range(n):
    for j in range(n):
        if i == j:
            pass
        else:
            ans += ((maps[i][0]-maps[j][0])**2 + (maps[i][1]-maps[j][1])**2) **(1/2)
			
num = 1
for k in range(1,n+1):
    num *= k
print(ans/n)

Submission status: Accepted

Solution code:
import itertools
import math

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

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

lists = itertools.permutations(range(N))

ans = 0
for l in lists:
    for i, x in enumerate(l):
        
        if i == 0:
            pre = P[x]
            continue

        temp = (P[x][0] - pre[0])**2 + (P[x][1] - pre[1])**2
        ans += math.sqrt(temp)
        pre = P[x]

print(ans / math.factorial(N))

Submission status: Accepted

Solution code:
import math

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

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

b = 0
for i in range(1,n):
    b += i

print(total*(n-1)/b)

Submission status: Accepted

Solution code:
N=int(input())
T=[list(map(int,input().split())) for i in range(N)]
X=0
c=1
for i in range(N):
  for j in range(N):
    X=X+((abs(T[i][0]-T[j][0]))**2+(abs(T[i][1]-T[j][1]))**2)**0.5
for r in range(1,N+1):
  c=c*r
print(X/N)

Submission status: Accepted

Solution code:
N=int(input())
z=[]
for  i in range(N):
    z.append(list(map(int,input().split())))
s=0
for i in range(N):
    for j in range(N):
        if i<j:
            s +=((z[i][0]-z[j][0])**2+(z[i][1]-z[j][1])**2)**0.5
print(2*s/N)

Submission status: Accepted

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    N = int(input())
    xy = XLMIIS(N)
    

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

    def f(n):
        ans = n
        if n <= 0:
            return 1
        for i in range(1,n):
            ans *= i
        return ans
    

    sumdis = 0
    for i in range(N):
        for j in range(i+1,N):
            sumdis += distance(xy[i][0],xy[i][1],xy[j][0],xy[j][1])
    summ = sumdis  / N * 2
    print(summ)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
data=[]
for i in range(n):
    data.append(list(map(int,input().split())))
ttl_len=0
for j in range(n):
    for k in range(n):
        if k<j:
            ttl_len+=2*((data[j][0]-data[k][0])**2+(data[j][1]-data[k][1])**2)**(1/2)
        else:
            continue
print(ttl_len/n)

Submission status: Accepted

Solution code:
import math
import itertools
import statistics

N = int(input())

# num = math.factorial(N)

cities_cord = []

for i in range(N):
    a = list(map(int,input().split()))
    cities_cord.append(a)
    
cities_no = list(range(N))

distance = []

for v in itertools.permutations(cities_no):
    all_dist = 0
    for i in range(len(v)-1):
        dist = math.sqrt((cities_cord[v[i]][0]-cities_cord[v[i+1]][0])**2 +
                         (cities_cord[v[i]][1]-cities_cord[v[i+1]][1])**2)
        all_dist += dist
        
    distance.append(all_dist)
    

print(statistics.mean(distance))

Submission status: Accepted

Solution code:
import math

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

for i in range(n):
    ix,iy=xy[i]
    tmp=[]
    for j in range(n):
        jx,jy=xy[j]
        tmp.append(math.sqrt((ix-jx)**2+(iy-jy)**2))
    l.append(tmp)

pat=1
for i in range(1,n+1):
    pat*=i
sa=1
for i in range(1, n-1):
    sa*=i
wei=pat/(n-1)-sa

sum=0
for i in range(n):
    for j in range(i+1, n):
        sum+=(wei*l[i][j])*2

print(sum/pat)

Submission status: Accepted

Solution code:
import itertools

if __name__ == '__main__':
    n = int(input())
    x, y = [], []
    for i in range(n):
        a, b = map(float, input().split())
        x.append(a)
        y.append(b)

    dp = []
    for i in range(n):
        xy = []
        for j in range(n):
            if i != j:
                xy.append(((x[i]-x[j])**2+(y[i]-y[j])**2)**0.5)
            else:
                xy.append(0)
        dp.append(xy)

    ave = 0.
    for v in itertools.permutations(range(n), n):
        for i in range(n-1):
            ave += dp[v[i]][v[i+1]]

    for i in range(1, n+1):
        ave /= i
    print(ave)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import math

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


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


ans = 0
for i in range(N):
    start = XY_list[i]
    for j in range(i+1, N):
        node = XY_list[j]
        ans += distance(start[0], start[1], node[0], node[1])

print(ans * 2 / N)

Submission status: Accepted

Solution code:
import math
N = int(input())
xy = [tuple(map(int, input().split())) for i in range(N)]
ans = 0
for i in range(N):
    for j in range(i+1, N):
        if i == j:
            continue
        else:
            ans += ((xy[i][0] - xy[j][0])**2 + (xy[i][1] - xy[j][1])**2)**0.5

print(ans*math.factorial(N-2)*(N-1) / math.factorial(N) * 2)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

N = int(input())

l = []
d = {}
for i in range(1, N+1):
    x, y = [int(n) for n in input().split(' ')]
    l.append(i)
    d[i] = (x, y)

temp = list(itertools.permutations(l))

length = []
for tmp in temp:
    length_i = 0
    for i in range(1, len(tmp)):
        length_i += np.sqrt((d[tmp[i]][0]-d[tmp[i-1]][0])**2+(d[tmp[i]][1]-d[tmp[i-1]][1])**2)
    length.append(length_i)

print(np.average(length))

Submission status: Accepted

Solution code:
import math

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

dis=[0]*(n*(n-1)//2)
k=0
for i in range(n):
    for j in range(i+1, n):
        dis[k] = math.sqrt(((city[i][0]-city[j][0])**2+(city[i][1]-city[j][1])**2))
        k+=1

ans=sum(dis)*2/n

print(ans)

Submission status: Accepted

Solution code:
import itertools
import math

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

seq = list()
for i in range(n):
    seq.append(i)

seq_all = list(itertools.permutations(seq))

ans = 0
for i in seq_all:
    for j in range(n - 1):
        end = i[j + 1]
        start = i[j]
        ans += math.sqrt((a[end][0] - a[start][0]) ** 2 + (a[end][1] - a[start][1]) ** 2)

print(ans / len(seq_all))

Submission status: Accepted

Solution code:
import itertools

N = int(input())

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

seq = range(0,N)
kumi = list(itertools.permutations(seq))

sum = 0
for k in kumi:
    for i, k_i in enumerate(k[:N-1]):
        n_i = k[i + 1]
        sum += ((X[k_i] - X[n_i]) ** 2 + (Y[k_i] - Y[n_i]) ** 2) ** 0.5

print(sum / len(kumi))


# print((2**0.5*4 + 8)/6)

Submission status: Accepted

Solution code:
import numpy as np
import sys
import math
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
XY = np.array(read().split(), np.int64)
X = XY[0::2]
Y = XY[1::2]

t = 0
for i in range(N):
    for j in range(i, N):
        t += math.sqrt((X[i] - X[j])**2 + (Y[i] - Y[j])**2)
print(2*t/N)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
n = int(input())
xy = []
ans_sum = 0
count = 0
for i in range(n):
    xy.append(list(map(int,input().split())))
for i in itertools.permutations(xy):
    ans = 0
    for j in range(n-1):
        ans += np.sqrt((i[j][0]-i[j+1][0])**2 + (i[j][1]-i[j+1][1])**2)
    count += 1
    ans_sum += ans
print("{:9f}".format(ans_sum/count))

Submission status: Accepted

Solution code:
import itertools

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

for i in range(n):
    x_, y_ = map(int,input().split())
    x.append(x_)
    y.append(y_)

li = list(range(n))
p = list(itertools.permutations(li))
di = 0
for i in p:
    i = list(i)

    for j in range(len(i)-1):
        xd = x[i[j]] - x[i[j + 1]]
        yd = y[i[j]] - y[i[j + 1]]
        di += (xd**2 + yd**2)**0.5

print(di/len(p))

Submission status: Accepted

Solution code:
import math
import itertools
N = int(input())
towns = [list(map(int, input().split())) for _ in range(N)]
seqs = list(itertools.permutations(range(N)))
length = 0
for seq in seqs:
    for i in range(1, N):
        x_s = towns[seq[i-1]][0]
        x_e = towns[seq[i]][0]
        y_s = towns[seq[i-1]][1]
        y_e = towns[seq[i]][1]
        length += math.sqrt((x_e-x_s)**2+(y_e-y_s)**2)
print(length/len(seqs))

Submission status: Accepted

Solution code:
import itertools

n = int(input())

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

dist_list = list()
dist_way = list(itertools.permutations(range(n)))

for dist_i in dist_way:
  dist = 0
  for i in range(len(dist_i)-1):
    dist += ((city_pos[dist_i[i]][0] - city_pos[dist_i[i+1]][0])**2 + (city_pos[dist_i[i]][1] - city_pos[dist_i[i+1]][1])**2)**(0.5)
  
  dist_list.append(dist)
  
print(sum(dist_list)/len(dist_list))

Submission status: Accepted

Solution code:
import itertools
import math

def main():
    n = int(input())
    ls = [list(map(int,input().split())) for i in range(n)]
    ans = 0
    comb = 0

    for i in itertools.permutations(range(n)):
        comb += 1
        for j in range(n-1):
            ans += math.sqrt((ls[i[j]][0]-ls[i[j+1]][0])**2 + (ls[i[j]][1]-ls[i[j+1]][1])**2)
    print(ans/comb)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
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())

x_p_list = list(itertools.permutations(x_list))
y_p_list = list(itertools.permutations(y_list))

n = math.factorial(N)

ans_list = []
for i in range(n): #順列
    ans=0
    for j in range(N-1): #その組み合わせ内
        x_l2 = (x_p_list[i][j] - x_p_list[i][j+1]) ** 2
        y_l2 = (y_p_list[i][j] - y_p_list[i][j+1]) ** 2
        ans += np.sqrt(x_l2 + y_l2)
    ans_list.append(ans)

print(sum(ans_list) / n)

Submission status: Accepted

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

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

pattern_list = list(itertools.permutations(seq_list))

distance = 0

for j in range(len(pattern_list)):
    distance_sum_tmp = 0
    for k in range(len(pattern_list[j])-1):
            index_from = pattern_list[j][k]
            index_to = pattern_list[j][k+1]
            distance_sum_tmp += (((xy_list[index_from][0] - xy_list[index_to][0]) ** 2 ) + ((xy_list[index_from][1] - xy_list[index_to][1]) ** 2 )) ** 0.5
    distance += distance_sum_tmp

print(distance / len(pattern_list))

Submission status: Accepted

Solution code:
import math

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

frac = math.factorial(N)
route_count = math.factorial(N-1)
sum = 0

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

print(sum/N)

Submission status: Accepted

Solution code:
import itertools

N = int(input())
X = []
Y = []

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


T = []
for i in range(N):
    T.append(i)

D = 0

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

for v in itertools.permutations(T, N):
    Dtmp = 0
    for j in range(N-1):
        Dtmp += dist(X[v[j]],X[v[j+1]],Y[v[j]],Y[v[j+1]])
    D += Dtmp

P = 1
for j in range(1,N+1):
    P *= j

output = D/P

print(output)

Submission status: Accepted

Solution code:
import sys
import itertools


def get_distance(from_town, to_town):
    distance = ((from_town[0] - to_town[0]) ** 2 + (from_town[1] - to_town[1]) ** 2) ** 0.5
    return distance


input = sys.stdin.readline

N = int(input())

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

patterns = itertools.permutations(townmap, N)

sum_v = 0
cnt_p = 0
for p in patterns:
    cnt_p += 1
    for i in range(len(p) - 1):
        sum_v += get_distance(p[i], p[i + 1])

result = sum_v / cnt_p

# print("len(patterns):{}".format(cnt_p))
print(result)

# print(get_distance([0, 0], [1, 0]))
# print(get_distance([1, 0], [0, 1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
import itertools
N = int(input())
town_dic = {}
for i in range(N):
    x, y = map(int, input().split())
    town_dic[i] = [x, y]

l = [i for i in range(N)]
case_list_list = itertools.permutations(l)
mean_distance = 0
temp_distance = 0
counter = 0
for case_list in case_list_list:
    counter += 1
    temp_distance = 0
    for i in range(N - 1):
        temp_distance += np.sqrt((town_dic[case_list[i]][0] - town_dic[case_list[i + 1]][0]) ** 2 + (town_dic[case_list[i]][1] - town_dic[case_list[i + 1]][1]) ** 2)
    mean_distance += temp_distance

print(mean_distance / counter)

Submission status: Accepted

Solution code:
import itertools, math

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

sum = 0
cnt = 0

for v in itertools.permutations(d, N):
  cnt += 1
  for i in range(N - 1):
    x1 = v[i][0]
    y1 = v[i][1]
    x2 = v[i + 1][0]
    y2 = v[i + 1][1]
    sum += math.sqrt((abs(x1 - x2)**2) + (abs(y1 - y2)**2))
print(sum / cnt)

Submission status: Accepted

Solution code:
import math
N=int(input())
S=list()
ans=0

const=math.factorial(N-1)*2/math.factorial(N)

for i in range(N):
    S.append(list(map(int,input().split())))


for i in range(N-1):
    for j in range(i+1,N):
        x1,y1=S[i]
        x2,y2=S[j]
        ans+=const*(((x1-x2)**2+(y1-y2)**2)**(1/2))

print(ans)

Submission status: Accepted

Solution code:
'''
def factorial(n):
    if n == 1:
        return n
    return n*factorial(n-1)
'''
n = int(input())
xy = [list(map(int,list(input().split()))) for i in range(n)]

sum = 0
for ida in range(n):
    for idb in range(n):
        if ida == idb: continue
        sum += ((xy[ida][0]-xy[idb][0])**2+(xy[ida][1]-xy[idb][1])**2)**0.5

ans = sum / n

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
x=[0]*n
y=[0]*n
sum=0

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

for i in range(n):
    for j in range(n):
        if j!=i:
            sum+=((x[i]-x[j])**2+(y[i]-y[j])**2)**0.5

print(sum/n)

Submission status: Accepted

Solution code:
import os
import math
import itertools
import numpy as np

N=int(input())
A=np.zeros((8,2)).astype(int)
for i in range(N):
  temp=list(map(int, input().split()))
  A[i,0]=temp[0]
  A[i,1]=temp[1]


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



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

tab=np.zeros((N,N))
for i in range(N):
  for j in range(i+1,N):
    tab[i,j]=distance(A[i,0],A[i,1],A[j,0],A[j,1])
    tab[j,i]=distance(A[i,0],A[i,1],A[j,0],A[j,1])
    
ret=0
C=math.factorial(N)      
for i in range(C):
  o=order[i]
  for j in range(1,N):
    ret+=tab[o[j],o[j-1]]
print(ret/C)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
import math
N=int(input())
B=[]
C=[1,2,3]
for i in range(N):
    A,C=map(int,input().split())
    B.append([A,C])


D=(list(itertools.permutations(range(N))))
#print(B)
#print(D)
#print(len(D))
total=0
for i in range(len(D)):
    for j in range(N-1):
        total+=math.sqrt((B[D[i][j]][0]-B[D[i][j+1]][0])*(B[D[i][j]][0]-B[D[i][j+1]][0])+(B[D[i][j]][1]-B[D[i][j+1]][1])*(B[D[i][j]][1]-B[D[i][j+1]][1]))
        #print(B[j][0],B[j][1])
        #print(B[j+1][0],B[j+1][1])
        #print('')

print(total/len(D))

Submission status: Accepted

Solution code:
import math
def permute(arr, s, n): 
    global result
    if (s == 1): 
        i=0
        distance=0
        while(i<n-1):
            distance+=math.sqrt(pow(A[arr[i]][0]-A[arr[i+1]][0],2)+pow(A[arr[i]][1]-A[arr[i+1]][1],2))
            i+=1
        result+=distance
        return
    for i in range(s): 
        permute(arr,s-1,n); 
        if s&1==1: 
            arr[0], arr[s-1] = arr[s-1],arr[0] 
        else: 
            arr[i], arr[s-1] = arr[s-1],arr[i] 

n=int(input())
A=[]
result=0
for i in range(n):
    x,y=list(map(int,input().split()))
    A.append([x,y])
permute([i for i in range(0,n)],n,n)
print(result/math.factorial(n))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
import math

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

def distance(i,j):
    return math.sqrt((x[i]-x[j])**2 + (y[i]-y[j])**2)

sum=0

for i in itertools.permutations(range(N),N):
    ret=0
    for j in range(N-1):
        ret+=distance(i[j],i[j+1])
    sum+=ret

div = math.factorial(N)
print(sum /div)

Submission status: Accepted

Solution code:
from itertools import combinations
import math
from statistics import mean

N = int(input())
l = []
ans = []
for i in range(N):
  l.append(list(map(int, input().split())))
  
for v in combinations(l, 2):
  ans.append(math.sqrt((v[0][0]-v[1][0])**2 + (v[0][1]-v[1][1])**2))
  
print(sum(ans)/N*2)

Submission status: Accepted

Solution code:

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


ANS = 0

def dfs(d, old, x):
	global ANS
	if sum(old)==N:
		ANS += d
		return

	for i in range(N):
		if not(old[i]):
			old[i]=True
			t = ((T[x][0]-T[i][0])**2 + (T[x][1]-T[i][1])**2)**.5
			dfs(d+t, old, i)
			old[i] = False


old = [False]*N

for i in range(N):
	old[i] = True
	dfs(0,old, i)
	old[i] = False

for i in range(1,N+1):
	ANS/=i
print(ANS)

Submission status: Accepted

Solution code:
import itertools
n = int(input())
temp = []
for i in range(n):
    x, y = map(int, input().split())   
    temp.append([x,y])

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

T = list(itertools.permutations(temp))

ans = 0
cnt = 0
for i in T:
    t = 0
    for j in range(1, len(i)):
        t += distance(i[j-1][0], i[j-1][1], i[j][0], i[j][1])
    cnt += 1
    ans += t
print(ans/cnt)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

lst = []
for I in list(itertools.permutations(range(N))):
    kyori = 0
    for i in range(N-1):
        kyori = kyori + ((X[I[i]]-X[I[i+1]])**2 +
                         (Y[I[i]]-Y[I[i+1]])**2) ** 0.5
    lst.append(kyori)

print(np.average(lst))