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:
from itertools import permutations
import math

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

l = list(permutations(XY, N))
sum = 0
for i in l:
    d = 0
    for j in range(len(i)-1):
        d += math.sqrt((i[j][0] - i[j+1][0]) ** 2 + (i[j][1] - i[j+1][1]) ** 2)
    sum += d
print(sum/len(l))

Submission status: Accepted

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

ans=cnt=0
for i in range(n-1):
  for j in range(i+1,n):
    ans+=((d[i][0]-d[j][0])**2+(d[i][1]-d[j][1])**2)**0.5
print(2*ans/n)

Submission status: Accepted

Solution code:
N = int(input())
ct = []

for i in range(N):
  ct.append([int(i) for i in input().split()])

dist = 0
for a in ct:
  for b in ct:
    dist += (abs(a[0] - b[0])**2 +abs(a[1] - b[1])**2)**0.5
print(dist/N)

Submission status: Accepted

Solution code:
from itertools import permutations

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

sum = 0
cnt = 0
for i in permutations(xy):
    for j in range(n - 1):
        sum += ((i[j][0] - i[j + 1][0]) ** 2 + (i[j][1] - i[j + 1][1]) ** 2) ** 0.5
    cnt += 1
print(sum / cnt)

Submission status: Accepted

Solution code:
import itertools

N = int(input())
cities = [list(map(int, input().split())) for _ in range(N)]
patterns = itertools.permutations(cities, N)
result = 0
count = 0
for ptn in patterns:
  count += 1
  dis = 0
  for i in range(N-1):
    dis += ((ptn[i][0]-ptn[i+1][0])**2 + (ptn[i][1]-ptn[i+1][1])**2)**0.5
  result += dis
print(result/count)

Submission status: Accepted

Solution code:
def dist(x, y, i, j):
    dx = x[i] - x[j]
    dy = y[i] - y[j]
    return (dx * dx + dy * dy) ** 0.5

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

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

ans = 0
for i in range(n):
    for j in range(i + 1, n):
       ans += dist(x, y, i, j) * 2 / n

print(ans)

Submission status: Accepted

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

ans = 0
t = 0
for i in permutations(xy, n):
  t += 1
  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/t)

Submission status: Accepted

Solution code:
import itertools
import math

n = int(input())

#座標のリスト
xy_list = []
for i in range(n) :
    xy_list.append(list(map(int, input().split())))

#順列を生成
per_list = []
for j in itertools.permutations([x for x in range(n)]) :
    per_list.append(j)

#順列に従って距離を加算
d = 0
for k in per_list :
    for l in range(n - 1) :
        d += math.sqrt((xy_list[k[l + 1]][0] - xy_list[k[l]][0]) ** 2 + (xy_list[k[l + 1]][1] - xy_list[k[l]][1]) ** 2)
        
print(d/(len(per_list)))

Submission status: Accepted

Solution code:
import itertools as it
import math
def Dist (x1,y1,x2,y2):
    dis = (x2 - x1)**2 + (y2 - y1)**2
    return math.sqrt(dis)
N = int(input())
Pos = []
res = 0
for i in range(N):
    pos = list(map(int,input().split()))
    Pos.append(pos)
array = list(it.permutations(i for i in range(N)))
for i in range(math.factorial(N)):
    for j in range(N-1):
        res += Dist(Pos[array[i][j]][0],Pos[array[i][j]][1],Pos[array[i][j+1]][0],Pos[array[i][j+1]][1])
print(res / math.factorial(N))

Submission status: Accepted

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

ans=cnt=0
for i in range(n):
  for j in range(i+1,n):
    ans+=((d[i][0]-d[j][0])**2+(d[i][1]-d[j][1])**2)**0.5
print(2*ans/n)

Submission status: Accepted

Solution code:
import math
import itertools

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

ans=cnt=0
for i in itertools.permutations([_ for _ in range(n)]):
  for j in range(n-1):
    x1,x2=d[i[j]][0],d[i[j+1]][0]
    y1,y2=d[i[j]][1],d[i[j+1]][1]
    ans+=math.sqrt((x1-x2)**2+(y1-y2)**2)
  cnt+=1
  #print(j,ans,cnt)
print(ans/cnt)

Submission status: Accepted

Solution code:
n = int(input())
x = []

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

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    X=[0]*N
    Y=[0]*N
    d=[[0]*N for _ in range(N)]
    for i in range(N):
        X[i],Y[i]=MI()
        
    for i in range(N):
        for j in range(N):
            dx=X[i]-X[j]
            dy=Y[i]-Y[j]
            d[i][j]=(dx**2 + dy**2)**0.5
            
    import itertools
    
    ans=0
    for ite in itertools.permutations(range(N), N):
        now=ite[0]
        for i in range(1,N):
            nxt=ite[i]
            ans+=d[nxt][now]
            now=nxt
    M=1
    for i in range(1,N+1):
        M*=i
    ans=ans/M
    print(ans)
            

main()

Submission status: Accepted

Solution code:
import itertools

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

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

sum = 0
LL = list(itertools.permutations(L))
for v in LL:
  x, y = xy[v[0]]
  for u in v[1:]:
    x2, y2 = xy[u]
    sum += ((x2 - x) ** 2 + (y2 - y) ** 2) ** 0.5
    x, y = x2, y2
  
ave = sum / len(LL)
print(ave)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
N = int(input())
xy = []
l = []
def comb(n,k):
  if n < k:
    n, K = k, N
  nu = 1
  de = 1
  for i in range(k):
    nu *= (N - i)
    de *= (K-i)
  return nu // de

for i in range(N):
  xy.append(list(map(int, input().split())))
for i in range(N-1):
  for j in range(i+1,N):
    l.append(math.sqrt((xy[i][0] - xy[j][0])**2 + (xy[i][1] - xy[j][1]) ** 2))

nu = math.factorial(N-2) * (N - 1) * 2
de = math.factorial(N)
ans = sum(l) * nu / de
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# Generated by https://github.com/kyuridenamida/atcoder-tools
from typing import *
import collections
import functools as fts
import itertools as its
import math
import sys
import numpy as np

INF = float('inf')


def solve(N: int, x: "List[int]", y: "List[int]"):
    def distance(x1, y1, x2, y2):
        return np.linalg.norm(np.array([x1, y1]) - np.array([x2, y2]))

    l = [[distance(x[i], y[i], x[j], y[j]) if j >
          i else 0 for j in range(N)] for i in range(N - 1)]

    return np.average([sum(l[r[i]][r[i+1]] if r[i] < r[i+1] else l[r[i+1]][r[i]] for i in range(N-1))
                       for r in its.permutations(range(N))])


def main():

    sys.setrecursionlimit(10 ** 6)

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    print(f'{solve(N, x, y)}')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import math

N=int(input())
X=[]
Y=[]
s=0
l=[int(x) for x in range(N)]
L = list(itertools.permutations(l, N))
for i in range(N):
    x,y=map(int,input().split())
    X.append(x)
    Y.append(y)
for i in range(math.factorial(N)):
    for j in range(N-1):
        s+=((X[L[i][j]]-X[L[i][j+1]])**2+(Y[L[i][j]]-Y[L[i][j+1]])**2)**0.5
print(s/(math.factorial(N)))

Submission status: Accepted

Solution code:
import itertools

N = int(input())
c = []
d = 0


for i in range(N):
  x1, y1 = map(int, input().split())
  c.append((x1,y1))
  
cp = list(itertools.permutations(c))
x = len(cp)

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

Submission status: Accepted

Solution code:
def abc145c_average_length():
    import itertools
    import math
    n = int(input())
    x = []
    y = []
    for _ in range(n):
        a, b = map(int, input().split())
        x.append(a)
        y.append(b)
    result = 0
    cnt = 0
    for p in itertools.permutations(range(n)):
        total = 0
        for i in range(n-1):
            total += math.sqrt(pow(x[p[i]]-x[p[i+1]], 2)+pow(y[p[i]]-y[p[i+1]], 2))
        result += total
        cnt += 1
    print(result/cnt)
abc145c_average_length()

Submission status: Accepted

Solution code:
import itertools
import math

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

S = 0
for P in itertools.permutations(range(N)):
    for i in range(N-1):
        s, t = P[i+1], P[i]
        S += math.sqrt((town[s][0]-town[t][0]) ** 2 + (town[s][1]-town[t][1]) ** 2)

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

print(S)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import itertools
import math
def input():
    return sys.stdin.readline()[:-1]

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

    l = [i for i in range(N)]
    p = [i for i in itertools.permutations(l, N)]
    d = 0
    for i in range(len(p)):
        t = p[i]
        for j in range(N - 1):
            d += math.sqrt(((x[t[j]] - x[t[j + 1]]) ** 2) + ((y[t[j]] - y
            [t[j + 1]])) ** 2)
    ans = d / math.factorial(N)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import math

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

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

ans = 0

for v in itertools.permutations(l):
    s = 0
    for i in range(n-1):
        s += d(v[i], v[i+1])
    ans += s

print(ans / math.factorial(n))

Submission status: Accepted

Solution code:
import itertools,math
N = int(input())
x = [0] * N
y = [0] * N
for i in range(N):
    x[i], y[i] = map(int, input().split())
seq=[]
for i in range(N):
    seq.append(i)
    
l=list(itertools.permutations(seq))

num=0
for i in l:
    for u in range(1,len(i)):
        num+=math.sqrt((x[i[u-1]]-x[i[u]])**2+(y[i[u-1]]-y[i[u]])**2)
print(num/len(l))

Submission status: Accepted

Solution code:
import itertools

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

LIS = [i for i in range(n)]

big_lis = list(itertools.permutations(LIS))
L = len(big_lis)


def sai(i, j):
    return (lis[A[i + 1]][j] - lis[A[i]][j]) ** 2


keep = 0
ANS = 0
for i in range(L):
    A = list(big_lis[i])
    keep = 0
    for j in range(n - 1):
        keep += (sai(j, 0) + sai(j, 1)) ** (1 / 2)
    ANS += keep
print(ANS / L)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from itertools import permutations
    from math import factorial

    N = int(readline())
    mat = []
    s = 0

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

    for per in permutations(range(N)):
        for i in range(N - 1):
            x1, y1 = mat[per[i]]
            x2, y2 = mat[per[i + 1]]
            s += ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5

    print(s / factorial(N))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

s = 0
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        s += ((town[i][0] - town[j][0])**2 + (town[i][1] - town[j][1])**2)**0.5

print(s / N)

Submission status: Accepted

Solution code:
import itertools
N = int(input())
z = []
for i in range(N):
  x,y = map(int,input().split())
  z.append((x,y))
ALL = 1
for i in range(N):
  ALL *= (i+1)
base = [i for i in range(N)]
A = list(itertools.permutations(base,N))
SUM = 0

def distance(a,b):
  ax = a[0]; ay = a[1]
  bx = b[0]; by = b[1]
  dis = ((ax-bx)**2 + (ay-by)**2)**(0.5)
  return dis

for X in A:
  now = z[X[0]]
  for i in range(1,N):
    nxt = z[X[i]]
    dif = distance(now,nxt)
    #print(dif)
    SUM += dif
#print(SUM,ALL)
ans = SUM/ALL
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    from itertools import combinations
    from math import sqrt

    N = int(input())
    xy = tuple(tuple(map(int, input().split())) for _ in range(N))

    ans = 0
    for can_move in combinations(xy, 2):
        xi, yi = can_move[0]
        xj, yj = can_move[1]
        ans += sqrt((xi - xj) ** 2 + (yi - yj) ** 2)
    print(f'{ans * 2 / N:.10f}')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    from itertools import combinations
    from math import sqrt

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

    ans = 0
    for can_move in combinations(xy, 2):
        xi, yi = can_move[0]
        xj, yj = can_move[1]
        ans += sqrt((xi - xj) ** 2 + (yi - yj) ** 2)
    print(f'{ans * 2 / N:.10f}')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    from itertools import permutations
    from math import sqrt

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

    ans = 0
    cnt = 0
    for can_order in permutations(xy):
        cnt += 1
        for k in range(1, N):
            xi, yi = can_order[k - 1]
            xj, yj = can_order[k]
            ans += sqrt((xi - xj) ** 2 + (yi - yj) ** 2)
    # print(ans / cnt)
    print(f'{ans / cnt:.10f}')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

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

distance = 0
for c in itertools.combinations(range(N), 2):
    c1, c2 = c
    distance += ((cities[c1][0] - cities[c2][0]) ** 2 + (cities[c1][1] - cities[c2][1]) ** 2) **0.5

answer = 2 * distance / N

print(answer)

Submission status: Accepted

Solution code:
import itertools

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

distance = 0
for c in itertools.combinations(range(N), 2):
    c1, c2 = c
    distance += ((cities[c1][0] - cities[c2][0]) ** 2 + (cities[c1][1] - cities[c2][1]) ** 2) **0.5

answer = 2 * distance / N

print(answer)

Submission status: Accepted

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

total_distance = 0
count = 0
for start in range(N-1):
    for end in range(start+1, N):
        start_x, start_y = towns[start]
        end_x, end_y = towns[end]

        total_distance += ((end_x - start_x)**2 + (end_y - start_y)**2)**0.5
        count += 1

answer = total_distance * ((N - 1) / count)
print(answer)

Submission status: Accepted

Solution code:
# import math

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

total_distance = 0
count = 0
for start in range(N-1):
    for end in range(start+1, N):
        start_x, start_y = towns[start]
        end_x, end_y = towns[end]

        total_distance += ((end_x - start_x)**2 + (end_y - start_y)**2)**0.5
        count += 1

# factor = math.factorial(N)

# answer = total_distance * (factor * (N - 1) / count) / factor
answer = total_distance * ((N - 1) / count)
print(answer)

Submission status: Accepted

Solution code:
import numpy as np
import math
n=int(input())
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))
a=np.array(a, dtype=object)
ans=0
for i in range(n):
  for j in range(n):
    if i==j:
      continue
    else:
      x= (a[i]-a[j])**2
      hei=math.sqrt(sum(x))
      ans+= hei/n
print(ans)

Submission status: Accepted

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

way = 0
p_list = [i for i in range(n)]
for P in itertools.permutations(p_list):
    for i in range(n-1):
        way += ((xy[P[i+1]][1]-xy[P[i]][1])**2+(xy[P[i+1]][0]-xy[P[i]][0])**2)**0.5

kai = 1
for i in range(n):
    kai *= (i+1)

print(way/kai)

Submission status: Accepted

Solution code:
import itertools
import math
#print(3 & (1 << 0))
def main():
    N = int(input())
    items = [i+1 for i in range(N)]

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

    paths =list(itertools.permutations(items))

    sum = 0
    for path in paths: # path = [1,2,3,4,5]
        for i in range(len(path)-1):
            from_idx = path[i] -1
            to_idx = path[i+1] -1
            xdiff= locations[from_idx][0] - locations[to_idx][0]
            ydiff= locations[from_idx][1] - locations[to_idx][1]
            sum = sum + math.sqrt(xdiff**2 + ydiff**2)
    print( sum / len(paths))
main()

Submission status: Accepted

Solution code:
import itertools
import math
N = int(input())
P = [0] * N 
for i in range(N):
    P[i] = list(map(int,input().split()))
distance = 0
for root in itertools.permutations(P,N):
    start = root[0]
    for r in root:
        distance += pow((r[0]-start[0])**2 + (r[1]-start[1])**2,1/2)
        start = r
print(distance/math.factorial(N))

Submission status: Accepted

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

Submission status: Accepted

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

N=int(input())
x = []
y = []
for _ in range(N):
    a,b = map(int,input().split())
    x.append(a)
    y.append(b)
ls = []
for arr in itertools.permutations(list(range(N))):
    l = 0
    for ii in range(len(arr)-1):
        i = arr[ii]
        j = arr[ii+1]
        d = ((x[i]-x[j])**2 + (y[i]-y[j])**2)**0.5
        l += d
    ls.append(l)

print(sum(ls)/len(ls))

Submission status: Accepted

Solution code:
import itertools
import math
N = int(input())
ls = []
ans = 0
for i in range(N):
  x,y = map(int,input().split())
  ls.append([x,y])
ls2 = []
for i in itertools.permutations(ls,N):
  ls2.append(list(i))
for i in range(math.factorial(N)):
  ls3 = ls2[i]
  now_x = ls3[0][0]
  now_y = ls3[0][1]
  for j in range(1,N):
    ans += ((now_x - ls3[j][0])**2 + (now_y - ls3[j][1]) ** 2)**0.5
    now_x = ls3[j][0]
    now_y = ls3[j][1]
print(ans/math.factorial(N))

Submission status: Accepted

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

waru = 1
for i in range(N):
    waru*= i+1
a = [i+1 for i in range(N)]
c = 0
su = 0
for i in permutations(a,N):
    li = list(i)
    for j in range(len(li)-1):
        start = l[li[j]-1]
        g = l[li[j+1]-1]
        su += math.sqrt((start[0]-g[0]) ** 2 + (start[1]-g[1]) ** 2)
print(su/waru)

Submission status: Accepted

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

Submission status: Accepted

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

dsum = 0

for i in range(n-1):
  for j in range(i+1, n):
    d = ( (xy[i][0] - xy[j][0])**2 + (xy[i][1] - xy[j][1])**2 )**0.5
    dsum += d

dave = dsum / (n*(n-1) / 2)

print(dave*(n-1))

Submission status: Accepted

Solution code:
import itertools

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


cnt=0
num=0
for v in itertools.permutations(xy):
  num+=1
  for i in range(n-1):
    a=(v[i][0]-v[i+1][0])**2+(v[i][1]-v[i+1][1])**2
    b=a**0.5
    cnt+=b

print(cnt/num)

Submission status: Accepted

Solution code:
def dist(a,b):
    return ((b[0]-a[0])**2+(b[1]-a[1])**2)**(1/2)
n=int(input())
loca=[list(map(int, input().split())) for _ in range(n)]
import itertools
a=[i for i in range(n)]
sum=0
cnt=0
for i in itertools.permutations(a):
    li=list(i)
    cnt += 1
    for i in range(1,n):
        a=loca[li[i-1]]
        b=loca[li[i]]
        sum+=dist(a,b)
print(sum/cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import itertools
def distance(p1, p2):
    return math.sqrt((p1[0]-p2[0])**2 + (p1[1] - p2[1])**2)
n = int(input())
adj = {}
for i in range(1, n+1):
    x, y = map(int, input().split())
    adj[i] = (x, y)
dd = {}
ans = 0
for i in range(1, n):
    for j in range(i+1, n+1):
        dist = distance(adj[i], adj[j])
        ans += dist
print(format((2 * ans) / n, '.10f'))

Submission status: Accepted

Solution code:
n=int(input())
import math
import itertools
zahyou=[[0,0]]
for i in range(n):
    tmp=[int(x) for x in input().split()]
    zahyou.append(tmp)

    ans=0
    
for seq in itertools.permutations(range(1,n+1)):
    dist=0
    for i in range(len(seq)-1):
        dist+=math.sqrt((zahyou[seq[i]][0]-zahyou[seq[i+1]][0])**2+(zahyou[seq[i]][1]-zahyou[seq[i+1]][1])**2)
    ans+=dist

print(ans/math.factorial(n))

Submission status: Accepted

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


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

for i in xy:
    for j in xy:
        cnt += np.linalg.norm(i - j)
print(cnt / N)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline.rstrip()
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n = inp()
XY = [(0,0)] + inplt(n)

P = permutations(range(1,n+1))
ans = 0
s = 0
for l in P:
    for i in range(1,n):
        s += math.sqrt((XY[l[i]][0]-XY[l[i-1]][0])**2 + (XY[l[i]][1]-XY[l[i-1]][1])**2)
        
ans = s/math.factorial(n)
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math

n = int(input())
points = [list(map(int, input().split())) for _ in range(n)]
numbers = list(range(1, n + 1))
diff = 0
count = 0
for pattern in itertools.permutations(numbers):
    count += 1
    for j in range(n - 1):
        points_index = pattern[j] - 1
        next_index = pattern[j + 1] - 1
        diff += math.sqrt((points[points_index][0] - points[next_index][0]) ** 2 + (points[points_index][1] - points[next_index][1]) ** 2)

print(diff / count)

Submission status: Accepted

Solution code:
#k = int(input())
#s = input()
#a, b = map(int, input().split())
#s, t = map(str, input().split())
#l = list(map(int, input().split()))
#l = [list(map(int,input().split())) for i in range(n)]
#a = [input() for _ in range(n)]

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


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

a = list(itertools.permutations(seq))
#print(a)

ans = 0
for i in a:
    for j in range(0,n-1):
        #idx1とidx2との距離
        ans += math.sqrt((l[i[j]][0] - l[i[j+1]][0])**2 + (l[i[j]][1] - l[i[j+1]][1])**2)


print(ans/len(a))

Submission status: Accepted

Solution code:
import itertools
import math

N=int(input())
zahyou=[list(map(int,input().split()))for i in range(N)]
jyunban=list(itertools.permutations(range(N)))
dist=list()
for i in range(len(jyunban)):
    tmp=0
    for j in range(N-1):
        tmp+=math.sqrt((zahyou[jyunban[i][j]][0]-zahyou[jyunban[i][j+1]][0])**2+(zahyou[jyunban[i][j]][1]-zahyou[jyunban[i][j+1]][1])**2)
    dist.append(tmp)
print(sum(dist)/math.factorial(N))

Submission status: Accepted

Solution code:
import itertools
import math

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

route = list(itertools.permutations([i for i in range(n)]))
for num in route:
    for i in range(1,n):
        dist += math.sqrt((xy[num[i]][0]-xy[num[i-1]][0])**2+ (xy[num[i]][1]-xy[num[i-1]][1])**2)
    
print(dist/len(route))

Submission status: Accepted

Solution code:
from math import sqrt
N = int(input())
X = []
Y = []
for i in range(N):
  x, y = map(int, input().split())
  X.append(x)
  Y.append(y)
ans = 0
for i in range(0, N-1):
  for j in range(i+1, N):
    ans += sqrt((X[i] - X[j]) ** 2 + (Y[i] - Y[j]) ** 2)
print(ans * 2.0 / N)

Submission status: Accepted

Solution code:
from itertools import permutations
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
ans = 0
li = list(permutations(range(N)))
l = len(list(permutations(range(N))))
for i in li:
    for j in range(N-1):
        x1, x2 = xy[i[j]][0], xy[i[j+1]][0]
        y1, y2 = xy[i[j]][1], xy[i[j+1]][1]
        ans += ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
print(ans/l)

Submission status: Accepted

Solution code:
#
# abc145 c
#

import sys
from io import StringIO
import unittest
import math
import itertools


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
0 0
1 0
0 1"""
        output = """2.2761423749"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2
-879 981
-866 890"""
        output = """91.9238815543"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """8
-406 10
512 859
494 362
-955 -475
128 553
-986 -885
763 77
449 310"""
        output = """7641.9817824387"""
        self.assertIO(input, output)


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

    R = itertools.permutations(range(N))

    all = 0
    for r in R:
        for pi in range(1, len(r)):
            all += math.sqrt((P[r[pi]][0]-P[r[pi-1]][0])**2 +
                             (P[r[pi]][1]-P[r[pi-1]][1])**2)

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

    print(f"{all/n:.10f}")


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
import math
n=int(input())
c=[]
for i in range(n):
  x,y=[int(x) for x in input().split()]
  c.append([x,y])
d=0
for i in range(n-1):
  for j in range(i+1,n):
    d+=math.sqrt((c[i][0]-c[j][0])**2+(c[i][1]-c[j][1])**2)
print(2*d/n)

Submission status: Accepted

Solution code:
import math
from itertools import permutations

def calc_distance(p1,p2):
    return  math.sqrt((p2[0]-p1[0])**2+(p2[1]-p1[1])**2)

def calc_distance_sum(position_arr,idx_arr):
    distance_sum = 0
    for i in range(len(idx_arr)-1):
        distance_sum += calc_distance(position_arr[idx_arr[i]],position_arr[idx_arr[i+1]])
    return distance_sum

if __name__ == "__main__":
    N = int(input())
    idx_list = [i for i in range(N)]
    idx_pattern_arr = list(permutations(idx_list))
    position_arr = [tuple(map(int,input().split())) for i in range(N)]
    distance_sum = 0
    for idx_pattern in idx_pattern_arr:
        distance_sum += calc_distance_sum(position_arr,idx_pattern)
    print(distance_sum/len(idx_pattern_arr))

Submission status: Accepted

Solution code:
import itertools
n = int(input())
seq = [i for i in range(n)]
steps = list(itertools.permutations(seq))
xy = [list(map(int,input().split())) for _ in range(n)]
sumlen = 0
for j in range(len(steps)):
    leng = 0
    step = steps[j]
    for k in range(n-1):
        x_1 = int(xy[step[k]][0])
        x_2 = int(xy[step[k+1]][0])
        y_1 = int(xy[step[k]][1])
        y_2 = int(xy[step[k+1]][1])
        leng += ((x_1 - x_2)**2  + (y_1 - y_2)**2)**0.5
    sumlen += leng
print((sumlen/len(steps)))

Submission status: Accepted

Solution code:
N = int(input())
xs, ys = [], []
for n in range(N):
  x, y = map(int, input().split(' '))
  xs.append(x)
  ys.append(y)
  
sum_dist = 0
for n1 in range(N-1):
  for n2 in range(n1+1, N):
    sum_dist += ((xs[n1]-xs[n2])**2 + (ys[n1]-ys[n2])**2)**(1/2)

# 辺abを通る組み合わせ数は，頂点a,bをセットと見た順列なので，2!(n-1)!．
# グラフは対称で全ての辺を同じ回数通るので，組み合わせの平均を考えると，
# ave_dist = 2!(n-1)!*sum_dist / n! = 2*sum_dist / n
print((2 * sum_dist) / N)