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 itertools
import math

N = int(input())
XY = [tuple(map(int, input().split())) for _ in range(N)]
cnt = 0
tot = 0
for arr in itertools.permutations(range(N)):
    now = XY[arr[0]]
    cnt += 1
    for i in arr[1:]:
        nex = XY[i]
        tot += math.sqrt(pow(now[0]-nex[0], 2)+pow(now[1]-nex[1], 2))
print(tot/cnt)

Submission status: Accepted

Solution code:
import numpy as np
n= int(input())
m = np.zeros((n,2))
sum1 = 0
count =0
for i in range(n):
    m[i] = list(map(int,input().split()))
for j in range(n):
    for k in range(j+1,n):
        sum1 = sum1 + ((m[j][0] - m[k][0])**2 + (m[j][1]-m[k][1])**2)**(1/2)
        count +=1

ans = 0

mul =1
for l in range(n):
    mul *= n-l
po =0
if n ==2:
    po = 1
elif n ==3:
    po =2
else:
    for m in range(n):
        po += m

ans = sum1*(n-1)/count
print(ans)

Submission status: Accepted

Solution code:
import sys
import time
import math
import itertools as it
def inpl():
    return list(map(int, input().split()))
st = time.perf_counter()
# ------------------------------

N = int(input())
x = [0] * N
y = [0] * N
for i in range(N):
	x[i], y[i] = map(int, input().split()) 
ls = [i for i in range(N)]
ans = 0
cnt = 0
for pm in it.permutations(ls):
	cnt += 1
	sm = 0
	for i, j in zip(pm, pm[1:]):
		sm += ((x[i]-x[j])**2 + (y[i]-y[j])**2)**0.5
	ans += sm
print(ans/cnt)

# ------------------------------
ed = time.perf_counter()
print('time:', ed-st, file=sys.stderr)

Submission status: Accepted

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

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

print(d * (n - 1) / cnt)

Submission status: Accepted

Solution code:
import math

def factorial(n):
    ans = 1
    for i in range(2, n+1):
        ans *= i
    return ans

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

sum_dist = 0
cnt = 0
for i in range(N):
    for j in range(i+1, N):
        sum_dist += math.sqrt((XY[i][0]-XY[j][0])**2 + (XY[i][1]-XY[j][1])**2)
        cnt += 1

print(sum_dist * (N-1) / cnt)

Submission status: Accepted

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

ans=0
nn=math.factorial(n)*2/n
for y in range(0,n-1):
  for z in range(y+1,n):
    p=a[y][0]
    q=a[y][1]
    s=a[z][0]
    t=a[z][1]
    u=(p-s)*(p-s)+(q-t)*(q-t)
    r=math.sqrt(u)
    
    ans+=r*nn
    
print(ans/math.factorial(n))

Submission status: Accepted

Solution code:
n = int(input())

pos = [[int(w) for w in input().split()] for _ in range(n)]

dist = [[0] * n for i in range(n)]

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

ave = sum(map(sum, dist))/((n**2-n)//2)

print(ave*(n-1))

Submission status: Accepted

Solution code:
import math

N=int(input())
x=[0]*N; y=[0]*N;
for i in range(N):
  x[i],y[i]=map(int,input().split())
count=[0]*N
for j in range(N):
  for k in range(N):
    if(k!=j):
      count[j]+=math.sqrt((x[j]-x[k])**2+(y[j]-y[k])**2)
res=0
for l in range(N):
  res+=count[l]
print(res/N)

Submission status: Accepted

Solution code:
import sys
from itertools import permutations
import math


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


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    c = [0] * n
    for i in range(n):
        x, y = map(int, input().split())
        c[i] = (x, y)
    ans = 0
    for p in permutations(range(n)):
        for i in range(1, n):
            ans += distance(*c[p[i]], *c[p[i - 1]])
    ans /= math.factorial(n)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import permutations
import math
from functools import lru_cache


@lru_cache(maxsize=None)
def distance(x1, y1, x2, y2):
    return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    c = [0] * n
    for i in range(n):
        x, y = map(int, input().split())
        c[i] = (x, y)
    ans = 0
    for p in permutations(range(n)):
        for i in range(1, n):
            ans += distance(*c[p[i]], *c[p[i - 1]])
    ans /= math.factorial(n)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools, math
N = int(input())
T = [list(map(int, input().split())) for i in range(N)]
d = 0
for l in itertools.permutations(range(N), N):
    for i in range(N - 1):
        d += math.sqrt((T[l[i]][0] - T[l[i + 1]][0]) ** 2 
        + (T[l[i]][1] - T[l[i + 1]][1]) ** 2)
print(d / math.factorial(N))

Submission status: Accepted

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

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)
INF = float("inf")

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

    ans = 0
    for i in range(N):
        xi,yi = XY[i]
        for j in range(i+1,N):
            xj,yj = XY[j]
            ans += ((xi-xj)**2 + (yi-yj)**2)**.5
    
    print(ans*2/N)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
from itertools import permutations
N = int(input())
C = [list(map(int, input().split())) for _ in range(N)]
perm = list(permutations(range(N)))
d = 0
for p in perm:
    for i in range(N - 1):
        d += math.sqrt((C[p[i]][0] - C[p[i + 1]][0]) ** 2 + (C[p[i]][1] - C[p[i + 1]][1]) ** 2)
print(d / len(perm))

Submission status: Accepted

Solution code:
from itertools import permutations 
s=""
n=int(input())
p=[]
for i in range(n):
    h,m=list(map(int,input().split()))
    p.append([h,m])
for i in range(n):
    s+=str(i+1)
a=[''.join(p) for p in permutations(s)] 
k=0
l=len(a)
import math
for i in range(l):
    z=0
    for j in range(n-1):
        x=int(a[i][j])-1
        y=int(a[i][j+1])-1
        z+=math.sqrt((p[x][0]-p[y][0])**2+(p[x][1]-p[y][1])**2)
    k+=z
        
print(k/l)

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


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


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    XY = [il() for _ in range(N)]

    ret = 0
    for x1, y1 in XY:
        for x2, y2 in XY:
            ret += calcTwoPointDistance(x1, y1, x2, y2)
    print(ret/N)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict, deque
from itertools import permutations

n = int(input())
s, ps = [tuple(map(int, input().split())) for i in range(n)], list(permutations([i for i in range(1, n + 1)]))

def dist(i, j):
    x, y = s[i][0] - s[j][0], s[i][1] - s[j][1]
    return (x ** 2 + y ** 2) ** 0.5

print(sum(sum(dist(p[i]-1, p[i+1]-1) for i in range(n-1)) for p in ps) / len(ps))

Submission status: Accepted

Solution code:
import math

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

num_nodes = n * (n - 1)
num_node_sel_total = math.factorial(n) * (n - 1)
num_node_sel = num_node_sel_total / num_nodes

ans = 0
for src in range(n):
    for dst in range(n):
        if src != dst:
            (src_x, src_y) = pts[src]
            (dst_x, dst_y) = pts[dst]
            d = math.sqrt((dst_x - src_x) ** 2 + (dst_y - src_y) ** 2)
            ans += d * num_node_sel
print(ans/math.factorial(n))

Submission status: Accepted

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

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

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

A = np.array(A)

L = list(it.permutations(range(0,N)))

distance = 0

for i in range (0, len(L)):
    for j in range (1, N):
        distance+=math.sqrt((A[L[i][j]][1]-A[L[i][j-1]][1])**2+(A[L[i][j]][0]-A[L[i][j-1]][0])**2)

print(distance/math.factorial(N))

Submission status: Accepted

Solution code:
###==================================================
### import
#import bisect
#from collections import Counter, deque, defaultdict
#from copy import deepcopy
#from functools import reduce, lru_cache
#from heapq import heappush, heappop
import itertools
import math
#import string
import sys
### stdin
def input(): return sys.stdin.readline().rstrip()
def iIn(): return int(input())
def iInM(): return map(int, input().split())
def iInM1(): return map(int1, input().split())
def iInLH(): return list(map(int, input().split()))
def iInLH1(): return list(map(int1, input().split()))
def iInLV(n): return [iIn() for _ in range(n)]
def iInLV1(n): return [iIn()-1 for _ in range(n)]
def iInLD(n): return [iInLH() for _ in range(n)]
def iInLD1(n): return [iInLH1() for _ in range(n)]
def sInLH(): return list(input().split())
def sInLV(n): return [input().rstrip('\n') for _ in range(n)]
def sInLD(n): return [sInLH() for _ in range(n)]
### stdout
def OutH(lst, deli=' '): print(deli.join(map(str, lst)))
def OutV(lst): print('\n'.join(map(str, lst)))
### setting
sys.setrecursionlimit(10 ** 6)
### utils
int1 = lambda x: int(x) - 1
### constants
INF = int(1e9)
MOD = 1000000007
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)
###---------------------------------------------------

N = iIn()
XY = iInLD(N)

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

ssum = 0
for i in range(len(lst)):
    for j in range(1,N):
        pre_x = XY[lst[i][j-1]][0]
        pre_y = XY[lst[i][j-1]][1]
        post_x = XY[lst[i][j]][0]
        post_y = XY[lst[i][j]][1]
        ssum += ((post_x - pre_x)**2 + (post_y - pre_y)**2)**0.5

ans = ssum / len(lst) * 1.0
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
N = int(input())
cc = []
dd = []
for i in range(N):
  aa = list(map(int,input().split()))
  cc.append(aa)
  dd.append(i)
ee = []
for i in permutations(dd):
  add = 0
  count = 0
  for j,k in enumerate(i):
    add += ((cc[k][0]-cc[i[j+1]][0])**2 + (cc[k][1]-cc[i[j+1]][1])**2)**0.5
    count += 1
    if count == N-1:
      break
  ee.append(add)
ff = 1
for i in range(1,N+1):
  ff *= i
print(sum(ee)/ff)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def calc(p1, p2):
    return ((((p1[0]-p2[0])**2) + ((p1[1]-p2[1])**2)))**0.5


def main():
    ans = 0
    N = int(input())
    l = [list(map(int, input().split())) for _ in range(N)]
    r = []
    for i in range(N-1):
        for j in range(i+1, N):
            r.append(calc(l[i], l[j]))
    ans = sum(r)*2/N
    print(f'{ans:.8f}')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
citys = [i for i in range(n)]
roots = list(itertools.permutations(citys))

sum = 0
for root in roots:
    for i in range(n-1):
        sum += ((xy[root[i]][0] - xy[root[i+1]][0])**2 + (xy[root[i]][1] - xy[root[i+1]][1])**2)**(0.5)


print(sum/len(roots))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import statistics
n=int(input())
xy=[]
for _ in range(n):
    xy.append(list(map(int,input().split())))
lis=list(range(n))
per_lis = itertools.permutations(lis)
dis_lis=[]
for one_case in per_lis:
    dis=0
    for i in range(n-1):
        ind=one_case[i]
        stx=xy[ind][0]
        sty=xy[ind][1]
        inde=one_case[i+1]
        gox=xy[inde][0]
        goy=xy[inde][1]
        
        X = (stx-gox)**2
        Y = (sty-goy)**2

        dis += math.sqrt(X+Y)
    dis_lis.append(dis)
print(statistics.mean(dis_lis))

Submission status: Accepted

Solution code:
import sys
import itertools
import numpy as np

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
basho = [LI() for _ in range(N)]
keiros = list(itertools.permutations(range(1,N+1)))
nagasa = []

for keiro in keiros:
    
    diff = 0
    for i in range(1,len(keiro)):
        
        diff += (((basho[keiro[i]-1][0] - basho[keiro[i-1]-1][0]) ** 2) + ((basho[keiro[i]-1][1] - basho[keiro[i-1]-1][1]) ** 2)) ** 0.5
        
    nagasa.append(diff)

num = np.array(nagasa)
print(np.average(num))

Submission status: Accepted

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


def TotalDis(L):
    D = 0
    for i in range(len(L) - 1):
        Xi, Yi = L[i]
        Xj, Yj = L[i+1]
        D += math.sqrt((Xj-Xi)**2 + (Yj-Yi)**2)
    return D


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

SumDis = 0
for l in itertools.permutations(P):
    SumDis += TotalDis(l)
ans = SumDis/math.factorial(N)

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt

def dist(A,B):
    p=A[0]-B[0]
    q=A[1]-B[1]
    return sqrt(p*p+q*q)

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

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

T=permutations(P,N)

D=0
for H in T:
    S=0
    for k in range(N-1):
        S+=dist(H[k],H[k+1])
    D+=S
print(D/f(N))

Submission status: Accepted

Solution code:
n=int(input())
a=[]
ans=0
for _ in range(n):
  x,y=map(int,input().split())
  for i,j in a:
    ans+=((i-x)**2+(j-y)**2)**.5
  a.append((x,y))
print(ans*2/n)

Submission status: Accepted

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

#n!を作成
n_sum = math.factorial(n)
#n個の要素で順列を作成
n_list = list(itertools.permutations(x_y,n))
ans = 0
#順列を選択
for i in range(len(n_list)):
	#順列内の要素を順番通りに選択し、ansに加算する
	#繰り返し回数はlen(n_list)-1
	tmp = copy.copy(n_list[i])
	for j in range(n-1):
		ans += math.sqrt((tmp[j][0] - tmp[j+1][0])**2 + ((tmp)[j][1] - tmp[j+1][1])**2)
print('{:.10f}'.format((ans/n_sum)))

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt

N = int(input())

town = []

for i in range(N):
    town.append(tuple([int(x) for x in input().split()]))

route_list = list(permutations(range(N)))

result = 0
for route in route_list:
    for i in range(1, N):
        x = (town[route[i-1]][0] - town[route[i]][0])**2
        y = (town[route[i-1]][1] - town[route[i]][1])**2

        result += sqrt(x + y)

print(result / len(route_list))

Submission status: Accepted

Solution code:
N=int(input())
L=[]
for i in range(N):
    x,y=list(map(int,input().split()))
    L.append([x,y])
D=[]
for i in range(N-1):
    for j in range(i+1,N):
        d=((L[i][0]-L[j][0])**2+(L[i][1]-L[j][1])**2)**0.5
        D.append(d)
Ave=sum(D)/len(D)
print(Ave*(N-1))

Submission status: Accepted

Solution code:
from itertools import permutations

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

nc=n
sm=1
while nc>=1:
    sm*=nc
    nc-=1

dis=0

for x in permutations(range(n)):
    for i in range(n-1):
        dis+=((lst[x[i+1]][0]-lst[x[i]][0])**2+(lst[x[i+1]][1]-lst[x[i]][1])**2)**0.5

print(dis/sm)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import itertools

def l2(z1, z2):
  return math.sqrt(pow(z1[0] - z2[0], 2) + pow(z1[1] - z2[1], 2))

n = int(input())
l = [list(map(int, input().split(' '))) for _ in range(n)]
seq_list = itertools.permutations(l, n)

dist = 0
for seq in seq_list:
  z_fr = []
  z_to = []
  
  for z in seq:
    z_fr = z_to
    z_to = z
    if len(z_fr)==0:
      continue
    dist += l2(z_fr, z_to)

print(dist/math.factorial(n))

Submission status: Accepted

Solution code:
from itertools import permutations

N = int(input())
xlist = []
ylist = []

n = 1
for i in range(1, N+1):
    x, y = map(int, input().split())
    xlist.append(x)
    ylist.append(y)
    n *= i

ans = 0
for perm in permutations(range(N)):
    for i in range(N-1):
        x1, y1 = xlist[perm[i]], ylist[perm[i]]
        x2, y2 = xlist[perm[i+1]], ylist[perm[i+1]]
        ans += ((x1 - x2)**2 + (y1 - y2)**2)**0.5 / n

print(ans)

Submission status: Accepted

Solution code:
import itertools,math
N = int(input())
ls = [list(map(int,input().split())) for _ in range(N)]
#print(ls)
ls2 = itertools.permutations(range(N))
#print(ls2)
dist = 0
for p in ls2:
    for i in range(N-1):
        j = i + 1
        dist += (((ls[p[i]][0])-(ls[p[j]][0]))**2+((ls[p[i]][1])-(ls[p[j]][1]))**2)**0.5
print(dist/math.factorial(N))

Submission status: Accepted

Solution code:
import math

N = int(input())

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

ans = 0

for i in range(N):
    for j in range(N):
        if i != j:
            x_distance = position_list[i][0] - position_list[j][0]
            y_distance = position_list[i][1] - position_list[j][1]
            ans += math.sqrt(x_distance**2 + y_distance**2)

print(ans/N)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import permutations

def solve(n,a):
    def dist(a1,a2):
        d2 = (a1[0]-a2[0])**2 + (a1[1]-a2[1])**2
        return d2 ** (1/2)
    
    l = []
    p_list = permutations(range(n))
    cnt = 0
    for p in p_list:
        s = 0
        for i in range(n-1):
            s += dist(a[p[i+1]],a[p[i]])
        l.append(s)
        cnt += 1
    return sum(l)/cnt


def main():
    N = int(input())
    a = [list(map(int,input().split())) for _ in range(N)]
    print(solve(N,a))
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

N = int(input())
Nlist = [list(map(int, input().split())) for i in range(N)]
total = 0
for i in range(N-1):
    for j in range(i + 1, N):
        total += math.sqrt((Nlist[i][0]-Nlist[j][0])**2 + (Nlist[i][1]-Nlist[j][1])**2)
        
ans = total*2/N
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import sqrt
from itertools import combinations

(n,), *xx = [list(map(int, s.split())) for s in open(0)]

tmp = 0

for i,j in combinations(range(n),2):
    xi, yi = xx[i]
    xj, yj = xx[j]
    tmp += sqrt((xi-xj)**2 + (yi-yj)**2)

print(tmp / n * 2)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)
import math
INF = 10**9
import itertools


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

    total = 0
    P = itertools.permutations(range(n))
    P = list(P)
    for i in range(len(list(P))):
        for j in range(n-1):
            total += math.sqrt((X[P[i][j]]-X[P[i][j+1]])**2 + (Y[P[i][j]]-Y[P[i][j+1]])**2)
    print(total/len(P))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
import math

N = int(input())
# S = input()
# n, *a = map(int, open(0))
# M, D = map(int, input().split())
# A = list(map(int, input().split()))
# S = input()
X = []
Y = []
for i in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)

tot = 0

_ = []
for i in range(N):
    _.append(i)
l = list(itertools.permutations(_))

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

for l_1d in l:
    for i in range(N - 1):
        tot += distance(x1 = X[l_1d[i + 1]], y1 = Y[l_1d[i + 1]], x2 = X[l_1d[i]], y2 = Y[l_1d[i]])

print(tot / len(l))

Submission status: Accepted

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

(n, ), *p = [[*map(int, i.split())] for i in open(0)]
m = 0.0
f = math.factorial(n - 1)*2
for i in range(n):
    for j in range(i + 1, n):
        m += ((p[i][0] - p[j][0])**2 + (p[i][1] - p[j][1])**2)**0.5*f
print(m / math.factorial(n))

Submission status: Accepted

Solution code:
import itertools

n = int(input())
p = [tuple(map(int, input().split())) for n_ in range(n)]
routes = [i for i in itertools.permutations(range(0,n), n)]

distances = 0
for route in routes:
    for i in range(len(route)-1):
        distances += ((p[route[i]][0] - p[route[i+1]][0])**2 + (p[route[i]][1] - p[route[i+1]][1])**2) ** 0.5

print(distances / len(routes))

Submission status: Accepted

Solution code:
from math import hypot, factorial


def dfs(d, p):
    if all(used):
        return d
    res = 0
    for i in range(n):
        if used[i]:
            continue
        used[i] = True
        res += dfs(d + hypot(x[i] - x[p], y[i] - y[p]), i)
        used[i] = False
    return res


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

ans = 0
used = [False] * n
for i in range(n):
    used[i] = True
    ans += dfs(0, i)
    used[i] = False
ans /= factorial(n)

print(ans)

Submission status: Accepted

Solution code:
import itertools
import math

N = int(input())

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

dis ={}

for i in range(len(town)):
    for j in range(i+1, len(town)):
        distance = math.sqrt((town[i][0] - town[j][0])**2 + (town[i][1] - town[j][1])**2)
        dis[str(i)+str(j)] = distance
        dis[str(j)+str(i)] = distance
permutations = list(itertools.permutations(list(range(N))))

all_dis = 0
for p in permutations:
    for i in range(len(p)-1):
        all_dis += dis[str(p[i])+str(p[i+1])]

print(all_dis / len(permutations))

Submission status: Accepted

Solution code:
import itertools

n = int(input())
town = [tuple(map(int,input().split())) for _ in range(n)]
c_town = list(itertools.combinations(town,2))
lp = len(list(itertools.permutations(town)))
sum_road = 0

for i in c_town:
  sum_road += ((i[0][0]-i[1][0])**2 + (i[0][1]-i[1][1])**2)**0.5
  
print(2*sum_road/n)

Submission status: Accepted

Solution code:
import itertools
import math

n = int(input())

xy = []

for i in range(n):
    a,b = map(int,input().split(" "))
    xy.append((a,b))
count = 0
res = 0.0
for v in itertools.permutations(list(range(0,n))):
    count += 1
    pre = v[0]
    for i in v[1:]:
        res += math.sqrt((xy[pre][0] - xy[i][0])**2 + (xy[pre][1] - xy[i][1])**2)
        pre = i
print(res/count)

Submission status: Accepted

Solution code:
N=int(input())
##c=list(map(int, input().split()))
 
a = [list(map(int, input().split())) for _ in range(N)]
 
k=0
for i in range(N):
    for j in range(N):
        if(i!=j):
            k=k+((a[i][0]-a[j][0])*(a[i][0]-a[j][0])+(a[i][1]-a[j][1])*(a[i][1]-a[j][1]))**0.5
 
print(k/N)

Submission status: Accepted

Solution code:
from itertools import permutations


def dfs(p, bit):
    res = 0
    for k in range(n):
        if bit >> k & 1:
            continue
        d = ((x[k] - x[p]) ** 2 + (y[k] - y[p]) ** 2) ** 0.5
        res += d + dfs(k, bit | (1 << k))
    return res


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):
#     ans += dfs(i, 1 << i)
# for i in range(n):
#     ans /= i + 1
for li in list(permutations(range(n), n)):
    tmp = 0
    for i in range(n - 1):
        p = li[i]
        k = li[i + 1]
        tmp += ((x[k] - x[p]) ** 2 + (y[k] - y[p]) ** 2) ** 0.5
    ans += tmp
for i in range(n):
    ans /= i + 1

print(ans)

Submission status: Accepted

Solution code:
import math
from itertools import permutations


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

total_distance = 0
num = 0
for perm_points in permutations(point, N):
    num += 1
    for i in range(N - 1):
        p1 = perm_points[i]
        p2 = perm_points[i + 1]
        total_distance += math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)

print(total_distance / num)

Submission status: Accepted

Solution code:
from itertools import permutations
from math import factorial
n = int(input())
town = [complex(*map(int,input().split())) for _ in range(n)]
d = 0
for l in permutations(town):
  for i in range(n-1):
    d += abs(l[i]-l[i+1])
print(d/factorial(n))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

# import math
import heapq

# input = sys.stdin.readline
from collections import deque


def main():
    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(N):
        for j in range(N):
            if i==j:
                continue
            ans += ((X[i]-X[j])**2 + (Y[i]-Y[j])**2 )**0.5

    print(ans/N)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools

N = int(input())
towns = [i for i in range(N)]

coordinates = {}
for i in range(N):
    tmp = list(map(int, input().split()))
    coordinates[i] = tmp

paths = list(itertools.permutations(towns, N))
distance = 0

for i in range(len(paths)):
    for j in range(N - 1):  # 街j, j+1の距離を加えていく
        town_now = paths[i][j]
        town_next = paths[i][j+1]
        distance += ((coordinates[town_now][0] - coordinates[town_next][0]) ** 2 +
                     (coordinates[town_now][1] - coordinates[town_next][1]) ** 2) ** (1/2)

avg_distance = distance / (len(paths))
print(avg_distance)

Submission status: Accepted

Solution code:
import itertools

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

cand = list(itertools.permutations(list(range(n)), n))

ans = 0
for cand_i in cand:
  for i in range(n-1):
    ans += ((XY[cand_i[i]][0]-XY[cand_i[i+1]][0])**2+(XY[cand_i[i]][1]-XY[cand_i[i+1]][1])**2)**(1/2)

print(ans/len(cand))

Submission status: Accepted

Solution code:
N=int(input())
position_list=[0]*N

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

import math
ans=0

for i in range(N):
    for j in range(N):
        if i != j:
            x_distance=position_list[int(i)][0]-position_list[int(j)][0]
            y_distance=position_list[int(i)][1]-position_list[int(j)][1]
            ans+=math.sqrt(x_distance**2+y_distance**2)

print(ans/N)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import math
import sys
from itertools import permutations

readlines = sys.stdin.buffer.readlines

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

total = 0
n = 0

for pattern in permutations(patterns):

    for i in range(len(pattern) - 1):
        town_a = pattern[i]
        town_b = pattern[i + 1]

        distance = math.sqrt((town_a[0] - town_b[0])**2 +
                             (town_a[1] - town_b[1])**2)
        total += distance

    n += 1

print(total / n)