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

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

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

p = permutations(range(n),n)

ans = 0
count = 0
for v in p:
  count+=1
  add = 0  
  for i in range(n-1):
    add += dd[v[i]][v[i+1]]
  ans += add
  
print(ans/count)

Submission status: Accepted

Solution code:
import math
import itertools

n = int(input())

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

l = list(itertools.permutations(xy, 2))

res = 0
for i in range(len(l)):
    x1, x2 = l[i][0][0], l[i][1][0]
    y1, y2 = l[i][0][1], l[i][1][1]

    res += math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)

print(res / n)

Submission status: Accepted

Solution code:
import itertools
import math
N = int(input())
# X1_list = [int(input()) for i in range(N)]
XY_list = [list(map(int,input().split())) for i in range(N)]
result = 0
for keiro in itertools.permutations(XY_list,N):
    for i in range(1,N):
        #print(keiro[i][0] - keiro[i-1][0], (keiro[i][1] - keiro[i-1][1]) ** 0.5)
        #print(keiro[i][0], keiro[i-1][0],keiro[i][1], keiro[i-1][1])
        #print(((keiro[i][0] - keiro[i-1][0]) ** 2 + (keiro[i][1] - keiro[i-1][1]) ** 2) ** 0.5)
        result += ((keiro[i][0] - keiro[i-1][0]) ** 2 + (keiro[i][1] - keiro[i-1][1]) ** 2) ** 0.5
print(result/math.factorial(N))

Submission status: Accepted

Solution code:
import math

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

for xs,ys in P:
  for x,y in P:
    ans += math.sqrt((xs-x)**2+(ys-y)**2)
  
print(ans/N)

Submission status: Accepted

Solution code:
from itertools import permutations
from math import factorial

n = int(input())
p = permutations(tuple(map(int, input().split())) for _ in range(n))
s=sum(((x1-x2)**2+(y1-y2)**2)**0.5 for a in p for(x1,y1),(x2,y2)in zip(a,a[1:]))
print(s / factorial(n))

Submission status: Accepted

Solution code:
n = int(input())
points = [[int(i) for i in input().split()] for _ in range(n)]

import functools
import itertools
import math

@functools.lru_cache()
def dist_calc(p1, p2):
    return math.sqrt((points[p1][0] - points[p2][0]) ** 2 + (points[p1][1] - points[p2][1]) ** 2)

dist = []
for route in itertools.permutations(range(n)):
    for i in range(n-1):
        dist.append(dist_calc(route[i], route[i+1]))

print(sum(dist)/math.factorial(n))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import itertools
import math

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

# solve
ans = 0
l = list()
for i in range(N):
    l.append(i)

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

# output
print(ans / len(ll))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
import functools
import itertools
import math
INF = float('inf')
MOD = 10**9+7

# nCk % mod
# def modCom(n, k, mod):
#     p, q = 1, 1
#     for i in range(n-k+1, n+1):
#         p = (p * i) % mod
#     for i in range(2, k+1):
#         q = (q * i) % mod
#     return p * pow(q, mod-2, mod) % mod
# 
# X, Y = map(int, input().split())
# l, r = -1, X//2
# while l+1 < r:
#     m = (l+r)//2
#     n = X-2*m
#     if 2*n+m > Y:
#         l = m
#     else:
#         r = m
# m = r
# n = X-2*r
# if 2*m+n == X and m+2*n == Y:
#     print(modCom(n+m, n, MOD))
# else:
#     print(0)


N = int(input())
xy = [None]*N
for i in range(N):
    x, y = map(int, input().split())
    xy[i] = (x, y)
ans = 0
for vs in itertools.permutations(xy, N):
    d = 0
    for v1, v2 in zip(vs, vs[1:]):
        d += ((v1[0]-v2[0])**2+(v1[1]-v2[1])**2)**0.5
    ans += d
for i in range(1, N+1):
    ans /= i
print(ans)



# r = int(input())
# print(r*r)

# 
# N = int(input())
# S = input()
# for i in range(N):
#     T = S[:i]
#     if T + T == S:
#         print('Yes')
#         exit()
# print('No')

Submission status: Accepted

Solution code:
n = int(input())

d = []

for i in range(n):
  t = input().split(" ")
  t = [float(j) for j in t]
  d.append(t)

dsum = 0

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

res = dsum / (n / 2)

print(res)

Submission status: Accepted

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

routesum = 0
for i in range(n-1):
    for j in range(i+1,n):
        routesum += ((arr[i][0]-arr[j][0])**2 + (arr[i][1]-arr[j][1])**2)**0.5
        
for i in range(1,n):
    routesum *= i
for i in range(1,n+1):
    routesum /= i

print(routesum*2)

Submission status: Accepted

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

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())
d = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        d += math.sqrt((x[i] - x[j])**2 + (y[i] - y[j])**2)
m = d * 2 / N
print(m)

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt

N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
sum_ = 0
l = list(permutations(XY))
len_l = len(l)
for perm in l:
    for i in range(N-1):
        sum_ += sqrt((perm[i+1][0] - perm[i][0])**2 + (perm[i+1][1] - perm[i][1])**2)
print(sum_ / len_l)

Submission status: Accepted

Solution code:
import math

n = int(input())
L = [list(map(int,input().split())) for i in range(n)]
Lsum = 0
Llen = 0
for i in range(n-1):
    for j in range(n-1-i):
        Lsum += math.sqrt((L[i][0]-L[i+j+1][0])**2 + (L[i][1]-L[i+j+1][1])**2)
        Llen += 1
print((Lsum/Llen)*(n-1))

Submission status: Accepted

Solution code:
import itertools
import math
N = int(input())
XY = [list(map(int,input().split())) for _ in range(N)]
#print(XY)

S = list(itertools.permutations(XY))
D = []
for s in S:
  #print(s)
  d = 0
  for i in range(1,len(s)):
      d += math.sqrt((s[i-1][0] - s[i][0])**2 + (s[i-1][1] - s[i][1])**2)
  D.append(d)
#print(D)
print(sum(D)/math.factorial(N))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

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

total = 0.0
for start in range(n):
    for end in range(start+1, n):
        dx = points[start][0] - points[end][0]
        dy = points[start][1] - points[end][1]
        dist = math.sqrt(dx*dx+dy*dy)
        total += dist / n
print(total*2)

Submission status: Accepted

Solution code:
n = int(input())
cities = [complex(*map(int, input().split())) for _ in range(n)]
facts = [1]
for i in range(1, n + 1):
    facts.append(facts[-1] * i)
ans = 0.
for i in range(n):
    ci = cities[i]
    for j in range(i + 1, n):
        cj = cities[j]
        dij = abs(ci - cj)
        ans += dij * facts[n - 1] * 2
print(ans / facts[n])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  l=[LI() for _ in range(n)]
  l2=[i for i in range(n)]

  sm=0
  for c in itertools.permutations(l2,n):
    _sm=0
    for i in range(n-1):
      a=l[c[i]]
      b=l[c[i+1]]

      _sm+=math.sqrt((a[0]-b[0])**2+(a[1]-b[1])**2)
    sm+=_sm

  return sm/math.factorial(n)

# main()
print(main())

Submission status: Accepted

Solution code:
import sys
import itertools
import math
N = int(input())
X = []
Y = []
for _ in range(N):
    x, y = [int(v) for v in input().split()]
    X.append(x)
    Y.append(y)

s = range(N)
ll = []
for l in itertools.permutations(s):
    d = 0
    for j in range(N - 1):
        d += math.sqrt((X[l[j]] - X[l[j + 1]]) * (X[l[j]] - X[l[j + 1]]) + (Y[l[j]] - Y[l[j + 1]]) * (Y[l[j]] - Y[l[j + 1]]))
    # print(l)
    # print(d)
    ll.append(d)
print(sum(ll) / len(ll))

Submission status: Accepted

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

from itertools import permutations

perms=permutations(xy)
dis=[]
for p in perms:
    d_tmp=[]
    for i in range(1,len(p)):
        d=((p[i][0]-p[i-1][0])**2+(p[i][1]-p[i-1][1])**2)**0.5
        d_tmp.append(d)
    dis.append(sum(d_tmp))
        
print(sum(dis)/len(dis))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
from math import *
n=int(input())
ps=[list(map(int,input().split())) for _ in range(n)]
perms = list(itertools.permutations(ps, n))
dists = []
for i in range(len(perms)):
  dist = 0
  cur = perms[i][0]
  for j in range(1,len(perms[i])):
    d = sqrt((perms[i][j][0]-cur[0]) ** 2 + (perms[i][j][1]-cur[1])**2)
    cur = perms[i][j]
    dist += d

  dists.append(dist)
print(sum(dists)/len(perms))

Submission status: Accepted

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

all_len = 0
p = list(itertools.permutations(range(n)))
for k in range(len(p)):
	for i in range(n-1):
		xi = xy[p[k][i]][0]
		xj = xy[p[k][i+1]][0]
		yi = xy[p[k][i]][1]
		yj = xy[p[k][i+1]][1]
		all_len += ((xi - xj)**2 + (yi - yj)**2)**0.5

print(all_len/len(p))

Submission status: Accepted

Solution code:
import sys
from itertools import permutations

def main():
    input = sys.stdin.readline
    N = int(input())
    pos = []
    for _ in range(N):
        x, y = map(int, input().split())
        pos.append((x, y))
    
    dists = []
    for root in permutations(range(N), N):
        d = 0
        for i in range(N-1):
            a = root[i]
            b = root[i+1]
            Xd = pos[a][0] - pos[b][0]
            Yd = pos[a][1] - pos[b][1]

            d += (Xd**2 + Yd**2)**0.5
        
        dists.append(d)
    
    return sum(dists) / len(dists)

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
N = int(input())
point = [list(map(int,input().split())) for _ in range(N)]
dis = [[0]*N for _ in range(N)]
for i in range(N):
  for j in range(i+1,N):
    dis[i][j] = ((point[i][0]-point[j][0])**2 + (point[i][1]-point[j][1])**2)**0.5
    dis[j][i] = dis[i][j]

cont = 0
for i in range(N):
  cont += sum(dis[i])

print(cont/N)

Submission status: Accepted

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

import math
import itertools

def main():
    n = int(input())

    x_list = []

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

    li = list(itertools.permutations(x_list))

    c = 0
    for l in li:
        for i, (x, y) in enumerate(l):
            if i+1 == n:
                break
            else:
                x1, y1 = l[i+1]
                c += math.sqrt((x1 - x)**2 + (y1 - y)**2)


    print(c / len(li))



if __name__ == '__main__':
    main()

Submission status: Accepted

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

dsum = 0.0
count = 0
for i in range(n):
    for j in range(i):
        d = ((p[i][0]-p[j][0])**2 + (p[i][1]-p[j][1])**2)**0.5
        dsum += d
        count += 1
print((n-1)*dsum/count)

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())
li=[]
for i in range(N):
  for j in range(i,N):
    if i!=j:
      li.append(((X[i]-X[j])**2+(Y[i]-Y[j])**2)**(1/2))
print(sum(li)*2*(N-1)/((N**2-N)))

Submission status: Accepted

Solution code:
import math
import itertools

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

def solve(N, P, INF=1000000):
    dist = [[0.0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if P[i] == P[j]:
                dist[i][j] = 0.0
            else:
                dist[i][j] = math.sqrt((P[i][0] - P[j][0])**2 + (P[i][1] - P[j][1])**2)
    
    cities = list(range(N))
    D = []
    for order in itertools.permutations(cities, N):
        d = 0.0
        for i in range(1, N):
            s = order[i-1]
            t = order[i]
            d += dist[s][t]
        D.append(d)
    return sum(D) / math.factorial(N)

if __name__ == '__main__':
    inputs = read()
    output = solve(*inputs)
    print("%.10f" % output)

Submission status: Accepted

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

Submission status: Accepted

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

def inasi(ls,i):
    n = []
    for j in range(len(ls)):
        if j == i:continue
        n.append(ls[j])
    return n

def kyori(ls):
    ans = 0
    for i in range(len(ls)-1):
        ans += math.sqrt((graph[ls[i]][0] - graph[ls[i+1]][0])**2 + (graph[ls[i]][1] - graph[ls[i+1]][1])**2)
    return ans

check = 0
count = 0
def keisan(n,pls,ls):
    global check,count
    if len(ls) == 0:
        check += kyori(pls)
        count += 1
        #pls.pop()
        return
    for i in range(len(ls)):
        pls.append(ls[i])
        keisan(n-1,pls,inasi(ls,i))
        try:pls.pop()
        except:pass
    return

keisan(10,[],[i for i in range(n)])
print(check/count)

Submission status: Accepted

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

import itertools
import math

ans = 0.0
i = 0
for route in itertools.permutations(town_list):
  i += 1
  before_town = False
  route_length = 0
  for town in route:
    if before_town is False:
      before_town = town
      continue
    route_length += math.sqrt(((before_town[0] - town[0]) ** 2) + ((before_town[1] - town[1]) ** 2))
    before_town = town
  ans += route_length

print(ans / i)

Submission status: Accepted

Solution code:
import math
import itertools

n = int(input())
t = [list(map(int, input().split())) for _ in range(n)]
d = 0
for i in range(n - 1):
    for j in range(i, n):
        d += (((t[i][0] - t[j][0]) ** 2 + (t[i][1] - t[j][1]) ** 2)
              ** 0.5) * ((n - 1) * math.factorial(n)/len(list(itertools.combinations(range(n), 2))))

print(d/math.factorial(n))

Submission status: Accepted

Solution code:
import itertools

n = int(input())

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

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

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

print(ans / c)

Submission status: Accepted

Solution code:
import itertools

N = int(input())

towns = []
for i in range(N):
    town = list(map(lambda x: int(x), input().split(" ")))
    towns.append(town)

p = list(itertools.permutations(towns))
result = 0
for nums in p:
    pre = None
    for num in nums:
        if pre is None:
            pre = num
            continue
        x = pow(pre[0] - num[0], 2)
        y = pow(pre[1] - num[1], 2)
        result += pow(x+y, 0.5)
        pre = num

result /= len(p)
print(result)

Submission status: Accepted

Solution code:
n=int(input())
dis=[]
for i in range(n):
  dis.append(list(map(int,input().split())))
import itertools
#print(dis)
l=[i for i in range(1,n+1)]

#for v in itertools.permutations(l,n):
#  print(v)
import math
p_list=itertools.permutations(l,n)
ans_l=[]
for mytuple in p_list:
  #print(mytuple)
  distance=0
  for k in range(1,n):
    now=mytuple[k]
    #print(now)
    bef=mytuple[k-1]
    #print(bef)
    distance+=math.sqrt((dis[now-1][0]-dis[bef-1][0])**2+(dis[now-1][1]-dis[bef-1][1])**2)
  #print(distance)
  ans_l.append(distance)
ans=sum(ans_l)/len(ans_l)
print("{:.11f}".format(ans))

Submission status: Accepted

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

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

amount = 0
for i in range(len(points)):
  for j in range(len(points)):
    if i == j:
      continue
    amount += distance(points[i],points[j])
print(amount/n)

Submission status: Accepted

Solution code:
import math
import itertools

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

z = []
cnt = 0
for v in itertools.permutations(li):
    cnt += 1
    for i in range(n-1):
        z.append(math.sqrt((v[i][0] - v[i+1][0])**2 + (v[i][1] - v[i+1][1])**2))
print(sum(z)/cnt)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

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

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

L2 = []
for i in range(N):
    for j in range(N):
        if i != j:
            L2.append(length(L[i][0], L[i][1], L[j][0], L[j][1]))

print(sum(L2)/N)

Submission status: Accepted

Solution code:
import math

def dist(XY, i, j):
  return math.sqrt((XY[i][0] - XY[j][0]) ** 2 + (XY[i][1] - XY[j][1]) ** 2)

N = int(input())
XY = [[0, 0] for _ in range(N)]
for i in range(N):
  XY[i] = [int(x) for x in input().split()]
D = [[0.0 for _ in range(N)] for _ in range(N)]
E = 0.0
for i in range(N):
  for j in range(N):
    E += dist(XY, i, j) / float(N)
print(E)

Submission status: Accepted

Solution code:
#  --*-coding:utf-8-*--

import math

def getSumOfD(N, XY, flags, n, d, x, y):
    if n == N:
        return d

    sumOfD = 0

    for i in range(N):
        if not flags[i]:
            flags[i] = True
            x2, y2 = XY[i]

            sumOfD += getSumOfD(
                N, XY, flags, n+1,
                d + math.sqrt((x2-x)**2 + (y2-y)**2),
                x2, y2)
            
            flags[i] = False
        
    return sumOfD


def getFact(n):
    x = 1
    for i in range(2, n+1):
        x *= i

    return x


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

    sumOfD = 0
    flags = [False]*N

    for i in range(N):
        flags[i] = True
        x, y = XY[i]
        sumOfD += getSumOfD(N, XY, flags, 1, 0, x, y)
        flags[i] = False

    print('{:.9f}'.format(sumOfD/getFact(N)));



if __name__ == '__main__':
    main()

Submission status: Accepted

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

for i in range(N):
    x, y = map(int, input().split())
    P.append((x, y))
d = 0
k = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        k += 1
        d += ((P[i][0] - P[j][0]) ** 2 + (P[i][1] - P[j][1]) ** 2) ** 0.5

print(d / k * (N - 1))

Submission status: Accepted

Solution code:
n= int(input())
s=0
a=[]


def solve(p):
	x,y = p[0][0], p[0][1]
	t=0
	for i in range(1,n):
		# print(x,y)
		t+= (( x- p[i][0])**2 + (y- p[i][1])**2)**0.5
		x= p[i][0]
		y= p[i][1]

	return t

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


z = list(itertools.permutations(a))

for i in z:
	# print(i)
	s+=solve(i)
# print(s)








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

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 fractions import gcd
 
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()))
import itertools
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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


N = INT()
b = []
for i in range(N):
  a = LIST()
  b.append(a)
# print(b)

jun = [i for i in range(N)]
c = list(itertools.permutations(jun))
# print(c)

ans2 = 0
for j in c:
  # tuple
  ans = 0
  # print(j)
  for i in range(len(j)-1):
    # print(j[i])
    # print(j[i+1])
    x1 = b[j[i]][0]
    x2 = b[j[i+1]][0]
    y1 = b[j[i]][1]
    y2 = b[j[i+1]][1]
    ans += dist(x1, x2, y1, y2)
    # print(ans)
  # print(ans)
  ans2 += ans
  # print(ans2)
    # print(dist(x1, x2, y1, y2))
print(ans2/len(c))

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

Kai = math.factorial(N)
C = N * (N-1) // 2
pathcount = Kai * (N-1) // C
Ans = 0
dist = 0

for j in range(N):
  for k in range(N):
    if j < k:
      dist = dist + ((x[j] - x[k]) ** 2 + (y[j] - y[k]) ** 2)** 0.5

Ans = dist * pathcount / Kai
print(Ans)

Submission status: Accepted

Solution code:
import math
n = int(input())
total = 0
towns = []
for _ in range(n):
    x, y = map(int, input().split())
    for t in towns:
        total += math.sqrt( (t[0]-x)**2 + (t[1]-y)**2 )
    towns.append([x,y])

print(total*2/n)

Submission status: Accepted

Solution code:
import itertools
import math
def distance(a,b,c,d):
    return ((a-c)**2 + (b-d)**2)**0.5
n = int(input())
x = [list(map(int,input().split())) for i in range(n)]
seq = [i for i in range(n)]
dis = 0
for s in list(itertools.permutations(seq)):
    for i in range(n-1):
        dis = dis + distance(x[s[i]][0],x[s[i]][1],x[s[i+1]][0],x[s[i+1]][1])
print(dis/math.factorial(n))

Submission status: Accepted

Solution code:
#N=int(input())
#A=list(map(int,input().split()))
def kyori(a,b):
	#print("plus:",a,b,"->",((a[0]-b[0])**2+(a[0]-b[0])**2)**0.5)
	return ((a[0]-b[0])**2+(a[1]-b[1])**2)**0.5
def bikkuri(n):
	if(n==1):
		return 1
	else:
		return n*bikkuri(n-1)
N=int(input())
zahyo=[[0,0]]*8
for i in range(N):
	zahyo[i]=list(map(int,input().split()))
goukei=0
for i in range(N):
	for j in range(N):
		goukei+=kyori(zahyo[i],zahyo[j])
print(goukei/N)
#N!*(N-1)個で平均はこれを(N!)で割る
#値はN*(N-1)/2種類
#つまり合計*(N-1)!/(N)!

Submission status: Accepted

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

import itertools
import math

ans = 0
for l in list(itertools.permutations(range(n))):
    tmp = 0
    for i in range(len(l) - 1):
        tmp += math.sqrt((xy[l[i]][0] - xy[l[i+1]][0]) ** 2 + (xy[l[i]][1] - xy[l[i+1]][1]) ** 2)
    ans += tmp
print(ans / len(list(itertools.permutations(range(n)))))

Submission status: Accepted

Solution code:
n = int(input())

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

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

Submission status: Accepted

Solution code:

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

res=0
def func(n):
	x=1
	for i in range(1,n+1):
		x*=i
	return x

for i in range(n-1):
	for j in range(i+1,n):
		res+=((xy[i][0]-xy[j][0])**2+(xy[i][1]-xy[j][1])**2)**0.5*2*func(n-1)
print(res/func(n))

Submission status: Accepted

Solution code:
import sys,itertools
def input():
    return sys.stdin.readline()[:-1]

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

MAP = [None]*N
for i in range(N):
    MAP[i] = [0]*N

for i in range(N):
    x_1,y_1 = dp[i]
    for j in range(N):
        x_2,y_2 = dp[j]
        if i==j:
            continue
        else:
            MAP[i][j] =((x_1-x_2)**2+(y_1-y_2)**2)**.5

cnt = 0
k = 0
for i in itertools.permutations(range(N)):
    tmp = 0
    c = 0
    for j in i:
        if c:
            tmp += MAP[pre][j]
        pre = j
        c += 1
    cnt += tmp
    k += 1
print(cnt/k)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
sys.setrecursionlimit(10 ** 7)

from math import factorial
from itertools import permutations

def main():
  n = ni()
  xy = [na() for _ in range(n)]

  ff = lambda a, b, c, d: ((a - b) ** 2 + (c - d) ** 2) ** 0.5

  res = []
  for per in permutations(range(n)):
    tmp = 0
    for i, pp in enumerate(per[:-1]):
      tmp += ff(xy[pp][0], xy[per[i+1]][0], xy[pp][1], xy[per[i+1]][1])
    res.append(tmp)
  print(sum(res) / factorial(n))


if __name__ == '__main__':
  main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import itertools
N = int(input())
X = []
Y = []

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

for lst in itertools.permutations(range(N)):
	for i in range(1, N):
		ret += math.sqrt((X[lst[i]] - X[lst[i - 1]]) ** 2 + (Y[lst[i]] - Y[lst[i - 1]]) ** 2)
		
print(ret / math.factorial(N))

Submission status: Accepted

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


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

    def distance(c1, c2):
        square_x = (c1[0] - c2[0]) ** 2
        square_y = (c1[1] - c2[1]) ** 2
        return (square_x + square_y) ** (1/2)

    total = [0] * N
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            total[i] += distance(coordinates[i], coordinates[j])

    print(sum(total)/N)


if __name__ == '__main__':
    answer()

Submission status: Accepted

Solution code:
import itertools
import math

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

point_index = list(range(N))

p = list(itertools.permutations(point_index))

total = 0
for lst in p:
    for i in range(N-1):
        distance = math.sqrt((point_list[lst[i]][0] - point_list[lst[i+1]][0])**2 + (point_list[lst[i]][1] - point_list[lst[i+1]][1])**2)
        total += distance

print(total / math.factorial(N))

Submission status: Accepted

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

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

s = 0

waru = math.factorial(N)
for v in itertools.permutations(xy, N):
    for i in range(len(v)-1):
        s += math.sqrt(pow(v[i][0]-v[i+1][0],2) + pow(v[i][1]-v[i+1][1],2))
print(float(s)/waru)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
n=int(input())

xy=[]

for i in range(n):
    xy.append(list(map(int,input().split())))

d=0

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

print(d*2/n)

Submission status: Accepted

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

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())
ans = 0
for i in range(n):
    for j in range(i+1,n):
        ans += 2/n * ( (x[i]-x[j])**2 + (y[i]-y[j])**2)**0.5
print(ans)