Problem:


Score : 300 points

Problem Statement

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

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

Constraints

2 \leq N \leq 8

-1000 \leq x_i \leq 1000

-1000 \leq y_i \leq 1000

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

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

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

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

Sample Input 1

3
0 0
1 0
0 1

Sample Output 1

2.2761423749

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

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

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

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

Sample Input 2

2
-879 981
-866 890

Sample Output 2

91.9238815543

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

Sample Input 3

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

Sample Output 3

7641.9817824387



Sample input:
3
0 0
1 0
0 1


Sample output:
2.2761423749

Submission status: Accepted

Solution code:
import sys, re, os
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
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
L = [LIST() for i in range(N)]

import itertools
l = [i for i in range(N)] #生成する数字
bit = list(permutations(l))
# print(bit)
cnt = 0
ans = 0
s = 0
for t in bit:
    # s = 0
    # print(t)
    for i in range(len(t)-1):
        # print(i)
        a, b = L[t[i]][0], L[t[i]][1]
        c, d = L[t[i+1]][0], L[t[i+1]][1]
        s += sqrt((a - c) ** 2 + (b - d) ** 2)
    # print(s)
    # ans += s
    # s = 0

ans = s / len(bit)
print(ans)

Submission status: Accepted

Solution code:
import math
import string
import collections
from collections import Counter


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
n = int(input())
tmp = [None]*n
for i in range(n):
    tmp[i] = [None]*2
# print(tmp)
for i in range(n):
    tmp[i][0], tmp[i][1] = map(int, input().split())
# print(tmp)
ans = 0
for i in range(n):
    for j in range(n):
        ans += ((tmp[i][0]-tmp[j][0])**2+(tmp[i][1]-tmp[j][1])**2)**0.5
print(ans/n)

Submission status: Accepted

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

ans = 0
for i in itertools.permutations(xy):
    for j in range(len(i)-1):
        ans += math.sqrt((i[j][0] - i[j+1][0])**2 + (i[j][1] - i[j+1][1])**2)

print(ans/math.factorial(n))

Submission status: Accepted

Solution code:
N = int(input())
XY = [list(map(int, input().split())) for i in range(N)]
s = 0
import math
for i in range(N):
  for j in range(i+1,N):
    s += math.sqrt((XY[i][0]-XY[j][0])**2+(XY[i][1]-XY[j][1])**2)
    

    
ans = s*2/N
print(ans)

Submission status: Accepted

Solution code:
import itertools

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


ans = 0
lis = [x for x in range(n)]
permutation = itertools.permutations(lis)


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


cnt = 0
for case in permutation:
    cnt += 1
    for i in range(n - 1):
        ans += dist(a[case[i]], a[case[i + 1]])
print(ans / cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code
import decimal 
import math
D=decimal.Decimal
def resolve():
    N,=pin()
    p=[tupin() for i in range(N)]
    ans=0
    for j in range(N):
        x,y=p[j]
        X,Y=D(x),D(y)
        for k in range(N):
            a,b=p[k]
            A,B=D(a),D(b)
            ans+=math.sqrt((X-A)**2+(Y-B)**2)
    print(float(ans/N))
#%%submit!
resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7
from math import sqrt, factorial
from itertools import permutations

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

def diff(i, j):
    tmp = (XY[i][0] - XY[j][0]) ** 2 + (XY[i][1] - XY[j][1]) ** 2
    return sqrt(tmp)


ans = 0

for tmp in permutations([i for i in range(N)]):
    score = 0
    for i in range(N - 1):
        score += diff(tmp[i], tmp[i + 1])
    ans += score

print (ans / factorial(N))

Submission status: Accepted

Solution code:
N = int(input())

xy = [list(map(int, input().split())) for _ in range(N)]
Ns = [i for i in range(N)]
from itertools import permutations
from math import factorial, sqrt
ans = 0
for lis in permutations(Ns):
    tmp = 0
    for i in range(1, N):
        x1, y1 = xy[lis[i-1]]
        x2, y2 = xy[lis[i]]
        tmp += sqrt((x2-x1)**2+(y2-y1)**2)
    ans += tmp

print(ans/factorial(N))

Submission status: Accepted

Solution code:
from itertools import permutations
def dist(x,y):
    return ((x[0]-y[0])**2+(x[1]-y[1])**2)**0.5
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
tot = 0
cnt = 0
for z in permutations(range(N)):
    cnt += 1
    for i in range(1,N):
        tot += dist(X[z[i]],X[z[i-1]])
print(tot/cnt)

Submission status: Accepted

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

ans = []
X = 0
for v in itertools.permutations(list(range(n))):
  cnt = 0
  X += 1
  for i in range(n-1):
    x1,y1 = xy[v[0]][0], xy[v[0]][1]
    x2,y2 = xy[v[1]][0], xy[v[1]][1]
    cnt += ((x1-x2)**2 + (y1-y2)**2)**0.5
  ans.append(cnt)
print(sum(ans)/X)

Submission status: Accepted

Solution code:
N = int(input())
L = [[int(l) for l in input().split()] for _ in range(N)]

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

import math
import itertools
List = [int(i) for i in range(N)]
ans = 0
for P in itertools.permutations(List):
    d = 0
    for j in range(N-1):
        d += f(L[P[j]][0], L[P[j]][1], L[P[j+1]][0], L[P[j+1]][1])
    ans += d
print(ans/math.factorial(N))

Submission status: Accepted

Solution code:
N = int(input())

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

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

ans = T*2/N
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import permutations

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    XY = [list(map(int, input().split())) for _ in range(n)]

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

    dist = 0
    cnt = 0
    for pattern in permutations(list(range(n))):
        cnt += 1
        for i in range(1, n):
            x1, y1 = XY[pattern[i - 1]]
            x2, y2 = XY[pattern[i]]
            dist += calc(x1, y1, x2, y2)

    print(dist / cnt)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import math
N = int(input())
ls1 = []
ls2 = []
for i in range(N):
    ls1.append(list(map(int,input().split())))
x = 0
y = 0
for i in range(N):
    for j in range(i+1,N):
        x = (ls1[i][0]-ls1[j][0])**2
        y = (ls1[i][1]-ls1[j][1])**2
        XY = math.sqrt(x+y)
        ls2.append(XY)
if len(ls2) == 1:
    print(ls2[0])
else:
    ans = sum(ls2)*2/N
    print(ans)

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

d = 0
import math
for i in range(N):
    for j in range(N):
        d += ((X[i]-X[j])**2+(Y[i]-Y[j])**2)**0.5

ans = d/N
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
XY = [tuple(map(int,input().split())) for i in range(N)]
import itertools
from math import hypot
sm = k = 0
for ptn in itertools.permutations(XY):
    k += 1
    for (x1,y1),(x2,y2) in zip(ptn,ptn[1:]):
        sm += hypot(x1-x2, y1-y2)
print(sm / k)

Submission status: Accepted

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

def main():
    N,*xy = map(int, read().split())

    XY = []
    for x, y in zip(*[iter(xy)]*2):
        XY.append((x, y))

    ans = 0
    n = factorial(N)
    for p in permutations(range(N)):
        tmp = 0
        for i in range(N-1):
            u, v = p[i], p[i+1]
            a, b = XY[u]
            c, d = XY[v]
            dist = sqrt((a - c)**2 + (b - d)**2)
            tmp += dist
        ans += tmp

    ans /= n
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
N=int(input())
X=np.array([list(map(int,input().split())) for i in range(N)])
print(sum(np.linalg.norm(i-j) for i in X for j in X)/N)

Submission status: Accepted

Solution code:
import math
N = int(input())
A = []
dist = []

#リストに値を入れる
for i in range(N):
    A.append(list(map(int,input().split())))

#距離を求める
for i in range(N-1):
    for j in range(i+1,N):
        dist.append(math.sqrt((A[j][0] - A[i][0])**2 + (A[j][1] - A[i][1])**2))
print((sum(dist) * 2) / N)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


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

    sum = 0

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

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


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np
n=int(input())
array=[]
x=[list(map(int,input().split())) for i in range(n)]
cnt=0
for xi, yi in x:
  for xj, yj in x:
    cnt+=((xi-xj)**2+(yi-yj)**2)**0.5
print(cnt/n)

Submission status: Accepted

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

kyi = 0
for i in range(n-1):
    for j in range(i+1,n):
        kyi += ((x[i]-x[j])**2 + (y[i]-y[j])**2)**0.5

print(kyi * 2 / n)

Submission status: Accepted

Solution code:
import itertools
import math

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

ans=0
num=0
for i in itertools.permutations(range(n), n):
    #print(i)
    num+=1
    sum=0
    for j in range(n-1):
        sum+=math.sqrt((xy[i[j+1]][0]-xy[i[j]][0])**2+(xy[i[j+1]][1]-xy[i[j]][1])**2)
    #print(sum)
    ans = ans/num * (num-1) + sum / num
    #print(ans)

print(ans)

Submission status: Accepted

Solution code:
import itertools
N=int(input())
XY=[]
for i in range(N):
  x,y=map(int,input().split())
  XY+=[[x,y]]
ALL=list(itertools.permutations(XY))
ans=10**9
d=0
for i in ALL:
  for k in range(N-1):
    d2=((i[k][0]-i[k+1][0])**2+(i[k][1]-i[k+1][1])**2)**(1/2)
    d+=d2
ans=d/len(ALL)
print(ans)

Submission status: Accepted

Solution code:
# N<=8　で　8! = 40000　程度なので全通り計算
import math
import itertools

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

# 順列を計算
s_per = list(itertools.permutations(s))
N = len(s_per)

dist = 0

# 全ての距離の足し合わせ
for i in range(N):
    for j in range(n-1):
        dist += math.sqrt((s_per[i][j+1][0] - s_per[i][j][0])**2 + (s_per[i][j+1][1] - s_per[i][j][1])**2)

# N!を求める
n_sum = 1
for i in range(n):
    n_sum *= (n-i)

print(dist/n_sum)

Submission status: Accepted

Solution code:
from itertools import permutations as per
from math import sqrt
n=int(input())
x=[]
y=[]
for _ in range(n):
    xx,yy=map(int,input().split())
    x.append(xx)
    y.append(yy)

sum=0
div=0
for jun in per(range(n)):
    div+=1
    for i in range(n-1):
        post=jun[i]
        pre=jun[i+1]

        sum+=sqrt((x[pre]-x[post])**2+(y[pre]-y[post])**2)

print(sum/div)

Submission status: Accepted

Solution code:
import math
import itertools

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

def kyori(junlist):
    sum=0
    for a in range(1,n):
        i=junlist[a-1]
        j=junlist[a]
        sum+=math.sqrt((xylist[i][0]-xylist[j][0])**2+(xylist[i][1]-xylist[j][1])**2)
    return sum

allsum=0
numlist=[i for i in range(n)]
junbanlist=[]
for v in itertools.permutations(numlist):
    junbanlist.append(list(v))

for jun in junbanlist:
    allsum+=kyori(jun)

print(allsum/math.factorial(n))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import itertools

# 入力
n = int(input())
point_list = []
for i in range(n):
    point = input()
    point_list.append(tuple(int(p) for p in point.split(' ')))

# 計算
count = 0
sum_distance = 0
for points in itertools.permutations(point_list):
    x1, y1 = points[0]
    count += 1
    for point in points[1:]:
        x2, y2 = point
        distance = math.sqrt(((x1 - x2) ** 2) + (y1 - y2) ** 2)
        sum_distance += distance
        x1, y1 = x2, y2
    
print(sum_distance / count)

Submission status: Accepted

Solution code:
n = int(input())
mp_l = [list(map(int,input().split())) for i in range(n)]
div = 1
for i in range(1,n+1):
    div *= i
all_cnt = 0
from itertools import permutations
import math
m_l = [[0]*n for i in range(n)]
def calc(a,b):
    if(m_l[a][b]!=0):
        return m_l[a][b]
    num = (mp_l[a][0]-mp_l[b][0])**2+(mp_l[a][1]-mp_l[b][1])**2
    d = math.sqrt(num)
    m_l[a][b],m_l[b][a] = d,d
    return d

for l in permutations(range(n),n):
    for i in range(n-1):
        all_cnt += calc(l[i],l[i+1])

print(all_cnt/div)

Submission status: Accepted

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

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

dist=0
for i in range(len(p)):
    for j in range(1,n):
        dist+=math.sqrt((xy[p[i][j-1]][0]-xy[p[i][j]][0])**2+(xy[p[i][j-1]][1]-xy[p[i][j]][1])**2)
print(dist/len(p))

Submission status: Accepted

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

dist = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        dist += math.sqrt((s[i][0]-s[j][0])**2 + (s[i][1]-s[j][1])**2)
ans = dist/n
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import collections
import numpy as np

rl = sys.stdin.readline
n = int(rl())
li = []
for _ in range(n):
  lis = list(map(int, rl().split()))
  li.append(lis)
t = 0
for i in list(itertools.permutations(range(n))):
  for k in range(n-1):
    s = (li[i[k]][0] - li[i[k+1]][0])**2 + (li[i[k]][1] - li[i[k+1]][1])**2
    t += s**0.5
print(t/math.factorial(n))

Submission status: Accepted

Solution code:
import numpy as np
n=int(input())
x=[0]*n
y=[0]*n
temp=[0]*n
for i in range(0,n):
  x[i],y[i]=map(int,input().split())
for i in range(0,n):
  for j in range(i+1,n):
    X=[abs(x[i]-x[j]),abs(y[i]-y[j])]
    temp.append(np.linalg.norm(X, ord=2))
print(sum(temp)*2/n)

Submission status: Accepted

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

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

from itertools import permutations
import math

lst=list(permutations(l))

ans_l=[]
len_l=len(lst)

for l_i in lst:
    tmp_dist=0
    for i in range(n-1):
        tmp_dist+=math.sqrt((xy[l_i[i]][0]-xy[l_i[i+1]][0])**2+(xy[l_i[i]][1]-xy[l_i[i+1]][1])**2)
    ans_l.append(tmp_dist)

print(sum(ans_l)/len_l)

Submission status: Accepted

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

dist = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        dist += math.sqrt((s[i][0]-s[j][0])**2 + (s[i][1]-s[j][1])**2)
ans = dist/n
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from itertools import permutations
from math import factorial
N = int(input())
places = [list(map(int, input().split())) for i in range(N)]
total = 0
for p in permutations(places):
  d = deque(p)
  departure = d.popleft()
  while d:
    arrival = d.popleft()
    total += ((departure[0] - arrival[0])**2 + (departure[1] - arrival[1])**2)**0.5
    departure = arrival
print(total / factorial(N))

Submission status: Accepted

Solution code:
import math

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


dist=0
a=math.factorial(n)
for i in range(n):
  for j in range(i+1,n):
    dist+=math.sqrt((s[i][0]-s[j][0])**2+(s[i][1]-s[j][1])**2)
print(dist*2/n)

Submission status: Accepted

Solution code:
from itertools import permutations
n = int(input())
xy = [[int(i) for i in input().split()] for _ in range(n)]

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

Submission status: Accepted

Solution code:
import math
n = int(input())
l = [list(map(int,input().split())) for _ in range(n)]
kumi= n*(n-1)/2 #階乗
keiro = math.factorial(n)
kaisu = keiro*(n-1)/kumi
total = 0

for i in range(n):
    a = 0
    for j in range(i+1,n):
        kyori = ((l[i][0]-l[j][0])**2+(l[i][1]-l[j][1])**2)**0.5
        a += kyori*kaisu
    total += a

print(total/keiro)

Submission status: Accepted

Solution code:
import itertools

def dist(F,G):
  x1=F[0]
  x2=G[0]
  y1=F[1]
  y2=G[1]
  return ((x1-x2)**2+(y1-y2)**2)**0.5

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


N=int(input())
A=[[0,0] for _ in range(N)]
for i in range(N):
  A[i][0],A[i][1]=map(int,input().split())
B=[]
for i in range(len(A)):
  B.append(i)


patterns=itertools.permutations(B)
totlen=0
avelen=0
for lis in patterns:
  for i,l in enumerate(lis[:-1]):
    for j in lis[i+1:]:
      totlen+=dist(A[l],A[j])
      break



avelen=totlen/(paths(N))
print(avelen)

Submission status: Accepted

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

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

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

total = 0
for v in itertools.permutations(l):
    for i in range(len(v)):
        if i == n-1:
            pass
        else:
            total += calc(town[v[i]][0],town[v[i+1]][0],town[v[i]][1],town[v[i+1]][1])

print (total/math.factorial(n))

Submission status: Accepted

Solution code:
import math
import itertools
n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
d=[0]*n

def distance(x1,x2,y1,y2):
    return math.sqrt(pow(x1-x2,2)+pow(y1-y2,2))
    
total= 0;
l=0
for i in range(n):
    d[i]=i
for b in itertools.permutations(d):
    l+=1
    #print(b)
    for i in range(n-1):
        total += distance(a[b[i+1]][0],a[b[i]][0],a[b[i+1]][1],a[b[i]][1])
    #    print(a[b[i+1]],a[b[i]])
     #   print(se)
print(total/l)

Submission status: Accepted

Solution code:
#factorial(9)でもうTLE
import itertools
import math

n = int(input())
lis = [x for x in range(1,n+1)]#順列とる数列
xy = [list(map(int,input().split())) for i in range(n)]#座標をメモ
permutations_lis = itertools.permutations(lis)#順列とって
l = list(permutations_lis)#全順列のリストを作る
ans = 0

for onecase in l: 
  s = 0
  for j in range(n-1):
    s += math.sqrt((xy[onecase[j]-1][0]-xy[onecase[j+1]-1][0])**2 + (xy[onecase[j]-1][1]-xy[onecase[j+1]-1][1])**2)
  ans += s
  
print(ans/math.factorial(n))

Submission status: Accepted

Solution code:
import itertools
import math

n = int(input())
lis = [x for x in range(1,n+1)] 
xy = [list(map(int,input().split())) for i in range(n)]
permutations_lis = itertools.permutations(lis)
l = list(permutations_lis)
ans = 0

for onecase in l: 
  s = 0
  for j in range(n-1):
    s += math.sqrt((xy[onecase[j]-1][0]-xy[onecase[j+1]-1][0])**2 + (xy[onecase[j]-1][1]-xy[onecase[j+1]-1][1])**2)
  ans += s
  
print(ans/math.factorial(n))

Submission status: Accepted

Solution code:
import itertools
import math

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

sum = 0
for j in itertools.permutations(z,n):
    j = list(j)
    for l in range(n-1):
        sum += ((xy[2*(j[l])]-xy[2*(j[l+1])])**2+(xy[2*(j[l])+1]-xy[2*(j[l+1])+1])**2)**0.5

print(sum/math.factorial(n))

Submission status: Accepted

Solution code:
N = int(input())

import math
import itertools

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

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

sum = 0
for i in per:
    for j in range(len(list(i))-1):
        x_ = x[i[j]] - x[i[j+1]]
        y_ = y[i[j]] - y[i[j+1]]
        sum += math.sqrt(x_**2 + y_**2)

print(sum / len(per))

Submission status: Accepted

Solution code:
import itertools
 
N = int(input())
xy = [0] * N
for i in range(N):
  xy[i] = list(map(int, input().split()))
  
lis = [x for x in range(N)] # 0からn-1までのリスト 
permutations_lis = itertools.permutations(lis)# 全ての場合のリストを生成
# 以下出力
divide = 0
ans = 0
for one_case in permutations_lis: 
  divide += 1
  #print(one_case)
  for i in range(len(one_case) - 1):
    #print(num)
    num = one_case[i]
    num2 = one_case[i + 1]
    ans +=  ((xy[num2][0] - xy[num][0]) ** (2) + (xy[num2][1] - xy[num][1]) ** (2)) ** (1/2)
    #print(ans)
#print(ans, divide)
print(ans / divide)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
import math

n = int(input())
coordinates = []

for i in range(n):
  x, y = map(int, input().split())
  coordinates.append([x, y])
# print(coordinates)
c = [num for num in range(n)]
pc = 0
dists = []
for p in itertools.permutations(c):
  pc += 1
  # print(p)
  dist = 0
  for i in range(n-1):
    a = coordinates[p[i]]
    b = coordinates[p[i+1]]
    dist += math.sqrt( ((b[0] - a[0]) ** 2) + ((b[1] - a[1]) ** 2))
  dists.append(dist)
print(sum(dists) / pc)
# print(dists)

Submission status: Accepted

Solution code:
import itertools
import math
n=int(input())
X=[list(map(int,input().split())) for _ in range(n)]
P=[i for i in range(n)]
total=0
for j in itertools.permutations(P,n):
  candi=list(j)
  for k in range(len(candi)-1):
    dis1=(X[candi[k]][0]-X[candi[k+1]][0])**2
    dis2=(X[candi[k]][1]-X[candi[k+1]][1])**2
    total+=(dis1+dis2)**(1/2)
print(total/math.factorial(n))

Submission status: Accepted

Solution code:
import math

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

dist = 0
from itertools import permutations
for p in permutations(town):
    for i in range(n-1):
         dist += math.sqrt((p[i][0] - p[i+1][0]) **2 + (p[i][1] - p[i+1][1]) **2)
ans = dist / math.factorial(n)
print(ans)
"""
dist = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        dist += math.sqrt((town[i][0] - town[j][0]) **2 + (town[i][1] - town[j][1]) **2)
ans = dist / n
print(ans)
"""

Submission status: Accepted

Solution code:
import math

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

dist = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        dist += math.sqrt((town[i][0] - town[j][0]) **2 + (town[i][1] - town[j][1]) **2)
ans = dist / n
print(ans)

Submission status: Accepted

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

dist=[[0]*N for _ in range(N)]
ans=0
for i in range(N):
  for j in range(N):
    if i==j:
      continue
    ans+=((AB[i][0]-AB[j][0])**2+(AB[i][1]-AB[j][1])**2)**0.5
ans/=N
print(ans)

Submission status: Accepted

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

from math import factorial as fac

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

total=fac(N)//fac(2)//fac(N-2)
print(((N-1)/(total))*S/2)

Submission status: Accepted

Solution code:
import math
from itertools import permutations

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

s = 0
count = 0
for routes in permutations(points):
    count += 1
    for p1, p2 in zip(routes, routes[1:]):
        x1, y1 = p1
        x2, y2 = p2
        s += math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)

print(s / count)

Submission status: Accepted

Solution code:
from math import sqrt
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-1):
    for j in range(i+1,n):
        x1,y1=p[i]
        x2,y2=p[j]
        d=sqrt((x1-x2)**2+(y1-y2)**2)
        ans+=d
ans/=n/2
print(ans)

Submission status: Accepted

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


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


City = []
for i in range(N):
    City.append(i)
ans = 0
for root in permutations(City):
    st = -1
    for i, r in enumerate(root):
        if i == 0:
            stx, sty = loc[r]
        else:
            nx, ny = loc[r]
            ans += calc_dist(stx, sty, nx, ny)
            stx = nx
            sty = ny
print(ans/math.factorial(N))

Submission status: Accepted

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

def kyori(s,g):
    return math.sqrt( (s[0] - g[0])**2 + (s[1] - g[1])**2)

def average_length(pos,n):
    amount = 0
    count = 0
    for i in itertools.permutations(pos,n):
        for j in range(len(i)-1):
            amount += kyori(i[j],i[j+1])
        count += 1
    return amount/count

if __name__ == "__main__":
    n = int(input())
    pos = []

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

    print(average_length(pos,n))

Submission status: Accepted

Solution code:
import itertools
import math

n = int(input())
cities = [list(map(int, input().split())) for i in  range(n)]
          
lis = [x for x in range(n)] # 0からn-1までのリスト
permutations_lis = itertools.permutations(lis)# 全ての場合のリストを生成

dist_list = []
for one_case in permutations_lis:
  dist = 0
  #print(one_case)
  for i, cur in enumerate(one_case):
    if i == 0:
      prev_city = cities[cur]
    else:
      cur_city = cities[cur]
      #print("check", prev_city, cur_city)
      dist += math.sqrt((cur_city[0] - prev_city[0])**2 + (cur_city[1] - prev_city[1])**2)
      #print(dist)
      prev_city = cur_city
  dist_list.append(dist)
    
print(sum(dist_list) / len(dist_list))

Submission status: Accepted

Solution code:
from itertools import permutations
import math


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

for perm in permutations(town):
    for i in range(N-1):
        total_dist += math.sqrt(
            (perm[i][0] - perm[i+1][0])**2 + 
            (perm[i][1] - perm[i+1][1])**2)


print(total_dist / math.factorial(N))

Submission status: Accepted

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

n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
p = [i for i in range(n)]
ans = 0
for pp in per(p, n):
    r = 0
    for j in range(n-1):
        r += sqrt((A[pp[j]][0] - A[pp[j+1]][0])**2 + (A[pp[j]][1] - A[pp[j+1]][1])**2)
    ans += r
print(ans/factorial(n))

Submission status: Accepted

Solution code:
import math

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n = ni()

x = []
y = []

for i in range(n):
  a,b = nm()
  x.append(a)
  y.append(b)

cnt = 0

def dist(xi,yi,xj,yj):
  return math.sqrt((xi-xj)**2+(yi-yj)**2)

def search(route):
  global cnt
  s = 0
  if len(route) == n:
    cnt += 1
    for i in range(n-1):
      s += dist(x[route[i]],y[route[i]],x[route[i+1]],y[route[i+1]])
    return s
  for i in range(n):
    if i not in route:
      s+=search(route+[i])
  return s

ans = search([])/cnt
print(ans)

Submission status: Accepted

Solution code:
import math
N = int(input())
city = [[] for _ in range(N)]
for i in range(N):
    a,b = map(int,input().split())
    city[i] = [a,b]
rout = [[0]*N for _ in range(N)]
total = 0
for i in range(N):
    for j in range(N):
        if city[i][0] == city[j][0] and city[i][1]==city[j][1]:
            continue
        else :
            sq = math.pow(city[i][0]-city[j][0],2) + math.pow(city[i][1]-city[j][1],2)
            total  += math.sqrt(sq)
print(total/N)

Submission status: Accepted

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