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
from math import factorial, sqrt

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

w = 0
for X in permutations(range(n)):
    x0, y0 = poses[X[0]]
    z = 0
    for i in X[1:]:
        x, y = poses[i]
        z += sqrt((x0-x)**2 + (y0-y)**2)
        x0, y0 = x, y
    w += z
print(w / factorial(n))

Submission status: Accepted

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

dis = 0

for x1, y1 in xy:
    for x2, y2 in xy:
        dis += ((x1 - x2)**2 + (y1 - y2)**2)**0.5

print(dis/n)

Submission status: Accepted

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

import math

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

ans = dist * 2 / N
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
chart = [[int(x) for x in input().split()] for _ in range(N)]
LL = []
for i in range(N):
    for j in range(i,N):
        LL.append(((chart[i][0]-chart[j][0])**2 + (chart[i][1]-chart[j][1])**2)**0.5)

def kaijo(N):
    ans = 1
    for i in range(1,N+1):
        ans = ans*i
    return ans

print(sum(LL)*2*kaijo(N-1)/kaijo(N))

Submission status: Accepted

Solution code:
import math
n = int(input())

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

# 順列計算
for i in range(n-1):
    for j in range(i+1, n):
        distance = math.sqrt((coord_list[i][0] - coord_list[j][0]) ** 2 + (coord_list[i][1] - coord_list[j][1]) ** 2)      
        all_distances += distance
        # print("i:{}, j:{} distance:{}".format(i, j, distance))

print(all_distances * 2 / n)

Submission status: Accepted

Solution code:
import math
import itertools
n = int(input())
a = []
for i in range(n):
	x,y = map(int, input().split())
	a.append([x,y])
x = 0
y = 0
s = 0
b = []
c = 0
for i in itertools.permutations(a):
	x = i[0][0]
	y = i[0][1]
	s = 0
	c += 1
	for xx,yy in i[1:]:
		s += math.sqrt((x-xx)**2 + (y-yy)**2)
		x = xx
		y = yy
	b.append(s)
print (sum(b)/c)

Submission status: Accepted

Solution code:
N = int(input())
town = [None]*N

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

avr_temp = 0
for i in range(N):
    for j in range(i+1, N):
        #町iから町jまでの距離を求める。
        avr_temp += ((town[i][0]-town[j][0])**2+(town[i][1]-town[j][1])**2)**0.5
avr = avr_temp * 2 / N
print(avr)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import math
def dist(A,B):
    a,b = A
    c,d = B
    return math.sqrt((a-c)**2 + (b-d) **2)
import itertools
N = int(input())
L = list(itertools.permutations([_ for _ in range(1,N+1)]))
res = 0
City = []
for _ in range(N):
    x,y = map(int,input().split())
    City.append((x,y))
for s in L:
    for i in range(0,len(s)-1):
        res += dist(City[s[i]-1],City[s[i+1]-1])
print(res/math.factorial(N))

Submission status: Accepted

Solution code:
import itertools, math

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

ans = 0
pat = list(itertools.permutations(city))
for c in pat:
  l = 0
  for j in range(N-1):
    l += math.sqrt(pow(c[j][1][0] - c[j+1][1][0], 2) + pow(c[j][1][1] - c[j+1][1][1], 2))
  ans += l
print(ans/len(pat))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import itertools
import math

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

p = itertools.permutations(p, n)

l = []
for i in p:
    temp = []
    for j in range(n-1):
        temp.append(math.sqrt((i[j][0] - i[j+1][0])**2 + (i[j][1] - i[j+1][1])**2))
    l.append(sum(temp))

print(sum(l) / len(l))

Submission status: Accepted

Solution code:
import math
N = int(input())
towns = []
dist = 0
for i in range(N):
	towns.append(list(map(int, input().split())))

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

print(dist * 2 / N)

Submission status: Accepted

Solution code:
N = int(input())
X_Y = [list(map(int, input().split())) for _ in range(N)]
root_Num = 0
total_root_Num = 1
for i in range(1,N):
    root_Num += i
for i in range(1,N+1):
    total_root_Num *= i
total_root_Num *= N-1
No = total_root_Num // root_Num 
dis = [0] * root_Num
total_dis = 0
for i in range(N):
    for j in range(i+1,N):
        total_dis += ((X_Y[i][0]-X_Y[j][0])**2 + (X_Y[i][1]-X_Y[j][1])**2)**(0.5)       
total_dis *= No
ans = total_dis/(total_root_Num /( N-1))
print(ans)

Submission status: Accepted

Solution code:
import math

def dis(x1, y1, x2, y2):
    return ((x1 - x2)**2 + (y1 - y2)**2) ** (1/2)

def kaijo(n):
    return math.factorial(n)

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

sum = 0

for j in range(n):
    for i in range(n):
        if i != j:
            sum = sum + (dis(x[i], y[i], x[j], y[j])) * kaijo(n-1)

print(sum/kaijo(n))

Submission status: Accepted

Solution code:
import math
n = int(input())
loc = list()

def getDist(x,y):
    return math.sqrt((x[0] - y[0])**2 + (x[1]-y[1])**2)

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

for i in range(n):
    x,y = list(map(int,input().split(" ")))
    loc.append((x,y))

total = 0
for i in range(n):
    for j in range(i):
        total += getDist(loc[i],loc[j]) * 2 * (n-1) * fac(n-2)

avg = total / fac(n)
print(avg)

Submission status: Accepted

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

n = int(input())
x = ["" for _ in range(n)]
y = ["" for _ in range(n)]

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

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

seq = list(range(n))
lis = list(itertools.permutations(seq))
#print(lis)

means = []
for s in lis:
    total_dist = []
    for i in range(len(s)-1):
        x1 = x[s[i]]
        x2 = x[s[i+1]]
        y1 = y[s[i]]
        y2 = y[s[i+1]]
        total_dist.append(dist(x1, x2, y1, y2))
    means.append(sum(total_dist))

print(sum(means)/len(means))

Submission status: Accepted

Solution code:
import numpy as np
import math
n=int(input())
e = [[int(i) for i in input().split()] for i in range(n)]

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

if n == 2:
  print(dist(0,1))
else:
  a = math.factorial(n-1)
  ans=0
  for i in range(n):
    for j in range(n):
      ans += dist(i,j) * a
  ans = ans / math.factorial(n)
  print(ans)

Submission status: Accepted

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

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

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

answer = 0
for i in range(N):
  for j in range(i + 1, N):
    answer += dist(XY[i], XY[j]) / (N / 2)

print(answer)

Submission status: Accepted

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

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

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

answer = 0
for i in range(N):
  for j in range(i + 1, N):
    answer += dist(XY[i], XY[j]) / (N / 2)

print(answer)

Submission status: Accepted

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

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

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

tmp = 0
for i in range(N):
  for j in range(i + 1, N):
    tmp += dist(XY[i], XY[j]) / (N / 2)

print(tmp)

Submission status: Accepted

Solution code:
import itertools
import math

N = int(input())

array = list(range(N))
ckyori_list = list(itertools.combinations(array, 2))
path_list = list(itertools.permutations(array))
kyori_list = [[ 0 for i in range(N)] for j in range(N)]

cmap = []
for i in range(N):
    temp = list(map(int, input().split(" ")))
    cmap.append(temp)
    
for i,j in ckyori_list:
    kyori_list[i][j] = math.sqrt((cmap[i][0]-cmap[j][0])**2 + (cmap[i][1]-cmap[j][1])**2)
    kyori_list[j][i] = kyori_list[i][j]

sum = 0
for i in path_list:
    for j in range(len(i)-1):
        sum += kyori_list[i[j]][i[j+1]]
        
print(sum/len(path_list))

Submission status: Accepted

Solution code:
import itertools
import math

N = int(input())
crd_list = []
for _ in range(N):
    crd_list.append([int(xy) for xy in input().split()])

cost_list = []
for way in itertools.permutations([n for n in range(N)]):
    cost = 0
    for index in range(1, N):
        cost += ((crd_list[way[index]][0]-crd_list[way[index-1]][0])**2 + (crd_list[way[index]][1]-crd_list[way[index-1]][1])**2)**0.5
    cost_list.append(cost)

print(sum(cost_list)/math.factorial(N))

Submission status: Accepted

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

MOD = 10 ** 9 + 7
import math

n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
s = sum([math.sqrt((xy[i][0] - xy[j][0]) ** 2 + (xy[i][1] - xy[j][1]) ** 2) for i in range(n) for j in range(n)])

ans = s / n

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
import math

def propare():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    
    tokens = iterate_tokens()
    N = int(next(tokens))
    x_list = []
    y_list = []
    for i in range(N):
        x_list.append(int(next(tokens)))
        y_list.append(int(next(tokens)))

    solve(N, x_list, y_list)

def solve(N: int, x_list: list, y_list: list):
    total_dist = 0
    for n_iter in itertools.permutations(range(N)):
        total_dist += measure_distance(n_iter, x_list, y_list)
    print(total_dist/math.factorial(N))
    return

def measure_distance(n_iter: tuple, x_list: list, y_list: list):
    dist = 0
    for i in range(len(n_iter)-1):
        tmp_dist_x = x_list[n_iter[i]] - x_list[n_iter[i+1]]
        tmp_dist_y = y_list[n_iter[i]] - y_list[n_iter[i+1]]
        dist += math.sqrt(tmp_dist_x**2 + tmp_dist_y**2)
    return dist

if __name__ == "__main__":
    propare()

Submission status: Accepted

Solution code:
import itertools
import math

N = int(input())
li = [list(map(int, input().split())) for k in range(N)]
r = []

total = []

for i in itertools.permutations(range(N)):
  r.append(i)


for i in r:
  count = 0
  for s in range(len(i)):
    if s + 1 > len(li) - 1:
      break

    town = i[s]
    nextTown = i[s+1]

    count += math.sqrt(((li[nextTown][0] - li[town][0]) ** 2) + ((li[nextTown][1] - li[town][1]) ** 2))

  total.append(count)

print(sum(total) / len(total))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import _collections
import string
from functools import lru_cache
import heapq

class cin():
    def int():
        return int(sys.stdin.readline().rstrip())
    def string():
        return sys.stdin.readline().rstrip()
    def mapInt():
        return [int(x) for x in cin.string().split()]
    def stringList(n):
        return [input() for i in range(n)]
    def intListList(n):
        return [cin.mapInt() for i in range(n)]
    def intColsList(n):
        return [int(input()) for i in range(n)]
        
class Math():
    def gcd(a,b):
        if b == 0:
            return a
        return Math.gcd(b,a % b)
    def lcm(a,b):
        return (a * b) // Math.gcd(a,b)
    def roundUp(a,b):
        return -(-a // b)
    def toUpperMultiple(a,x):
        return Math.roundUp(a,x) * x
    def toLowerMultiple(a,x):
        return (a // x) * x
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

MOD = int(1e09) + 7

def main():
    N = cin.int()
    X = cin.intListList(N)
    R = list(itertools.permutations(range(N)))
    ans = 0
    for p in R:
        l = 0.0
        for i in range(N - 1):
            x = X[p[i + 1]][0] - X[p[i]][0]
            y = X[p[i + 1]][1] - X[p[i]][1]
            l += (x ** 2 + y ** 2) ** 0.5
        ans += l
    ans /= len(R)
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def permutation(lst):
    if len(lst) == 0:
        return []
    if len(lst) == 1:
        return [lst]
    res = []
    for i in range(len(lst)):
       m = lst[i]
       remLst = lst[:i] + lst[i+1:]
       for p in permutation(remLst):
           res.append([m] + p)
    return res

dist = lambda x1, y1, x2, y2 : ((x1-x2)**2 + (y1-y2)**2)**.5
n = int(input())
d = [[0] * n for _ in range(n)]
pnts = []
for _ in range(n):
	x, y = map(int, input().split())
	pnts.append((x, y))
for i in range(n):
	for j in range(n):
		d[i][j] = d[j][i] = dist(pnts[i][0], pnts[i][1], pnts[j][0], pnts[j][1])
paths = permutation(list(range(n)))
res = 0
for path in paths:
    for j in range(n-1):
        res += d[path[j]][path[j+1]]
print(round(res/len(paths), 6))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Jan 24 18:25:41 2020
abc145c
@author: manakamura
"""

n = int(input())

x=[]
y=[]
for i in range(n):
    tmp = input().split()
    a,b = list(map(lambda a: int(a), tmp))
    x.append(a)
    y.append(b)
#    print(a,b)

dis=[]

sum=0
for i in range(0,n):
    tmp=[]
    for j in range(0,i):
        tmp.append(dis[j][i])
    tmp.append(1)
    for j in range(i+1,n):
        l=0
        l+=(x[j]-x[i])**2
        l+=(y[j]-y[i])**2
        l=l**0.5
        sum+=l
        tmp.append(l)
#    print(tmp)
    dis.append(tmp)

#print(dis)

print(sum*2/n)

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

Submission status: Accepted

Solution code:
import math
import itertools

n = int(input())
List = [list(map(int, input().split())) for i in range(n)]
dis_sum, count = 0, 0
for v in itertools.permutations(List):
    for i in range(len(v)-1):
        z = (v[i][0]-v[i+1][0])**2 + (v[i][1]-v[i+1][1])**2
        dis = math.sqrt(z)
        dis_sum += dis
    count += 1
print(dis_sum/count)

Submission status: Accepted

Solution code:
import itertools
from itertools import permutations
from math import factorial, hypot

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

for i in range(n):
    x1, y1 = [int(j) for j in input().split()]
    x.append(x1)
    y.append(y1)

ans = 0

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

for status in itertools.permutations(order, n):
    tmp = 0
    for i in range(n - 1):
        tmp += hypot(x[status[i]] - x[status[i + 1]], y[status[i]] - y[status[i + 1]])
    ans += tmp

print(ans / factorial(n))

Submission status: Accepted

Solution code:
import itertools
import math
N = int(input())
A = []
ans = 0
t = 0
for _ in range(N):
  a = list(map(int,input().split()))
  A.append(a)
def D(x0,y0,x1,y1):
  d = math.sqrt((x1-x0)**2+(y1-y0)**2)
  return d

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

for row in itertools.permutations(r,N):
  t += 1
  for i in range(N-1):
    p = row[i]
    q = row[i+1]
    x0,y0 = A[p]
    x1,y1 = A[q]
    ans += D(x0,y0,x1,y1)

print(ans/t)

Submission status: Accepted

Solution code:
from math import factorial

N = int(input())
li = [[int(zz) for zz in input().split()] for _ in range(N)]

ans = 0
for i in range(N):
    for j in range(i+1,N):
        ans += ((li[i][0]-li[j][0])**2+(li[i][1]-li[j][1])**2)**(1/2)

print(ans*2/N)

Submission status: Accepted

Solution code:
n = int(input())
# distance_matrix = [[0] * n for i in range(n)]
cordinates = [[0] * 2 for i in range(n)]
for i in range(n):
  cordinates[i][0], cordinates[i][1] = map(int, input().split())

sum = 0
for i in range(n):
  for j in range(n):
    #distance_matrix[i][j] = ((cordinates[i][0] - cordinates[j][0])**2 + (cordinates[i][1] - cordinates[j][1])**2)**0.5
    sum += (n-1)*(((cordinates[i][0] - cordinates[j][0])**2 + (cordinates[i][1] - cordinates[j][1])**2)**0.5)

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

Submission status: Accepted

Solution code:
import math
n = int(input())
p = {}
for i in range(n):
    x,y = map(int, input().split())
    p[i] = (x, y)
ave = 0
for i in range(n):
    for j in range(i+1,n):
        ave += math.sqrt(abs(p[i][0] - p[j][0])**2 + abs(p[i][1] - p[j][1])**2)
ave /= ((n*(n-1))/2)
total = ave*(n-1)
print(total)

Submission status: Accepted

Solution code:
from itertools import permutations
from math import factorial
N=int(input())
D=[tuple(map(int,input().split())) for _ in range(N)]
ans=0
for d in permutations(D):
    for i in range(N-1):
        ans+=((d[i][0]-d[i+1][0])**2+(d[i][1]-d[i+1][1])**2)**0.5
print(ans/factorial(N))

Submission status: Accepted

Solution code:
n = int(input())
ll = [list(map(int,input().split())) for _ in range(n)]
d = 0
for x1,y1 in ll:
  for x2,y2 in ll:
    d += ((x1-x2)**2+(y1-y2)**2)**0.5
print(d/n)

Submission status: Accepted

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

import itertools as it
lt = list(it.permutations(range(0, n)))

def dist(i, j):
  return ((ll[i][0]-ll[j][0])**2 + (ll[i][1]-ll[j][1])**2)**0.5

d = 0

for t in lt:
  for i in range(n-1):
    d += dist(t[i], t[i+1])

print(d/len(lt))

Submission status: Accepted

Solution code:
import math

n = int(input())
List = [list(map(int, input().split())) for i in range(n)]
dis_list = []
for i in range(n):
    for j in range(n):
        if i != j:
            z = (List[i][0]-List[j][0])**2 + (List[i][1]-List[j][1])**2
            dis = math.sqrt(z)
            dis_list.append(dis)
print(sum(dis_list)/n)

Submission status: Accepted

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

total_length = 0
for i in range(n):
    position = list(map(int, input().split()))
    town_map.append(position)
    for j in range(i):
        total_length += ((position[0] - town_map[j][0]) ** 2 + (position[1] - town_map[j][1]) ** 2) ** (1/2)

print(total_length * 2 / n)

Submission status: Accepted

Solution code:
import itertools
import math

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

def dist_p(p1, p2):
    return dist(p1[0], p2[0], p1[1], p2[1])

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

for i in range(n):
    xi,yi = map(int, input().split())
    c.append((xi, yi))

l = list(itertools.permutations(c))

sum = 0
for e in l:
    for i in range( len(e)-1 ):
        sum += dist_p(e[i], e[i+1])

print(sum/len(l))

Submission status: Accepted

Solution code:
import itertools,math
N=int(input())
T=[list(map(int,input().split())) for i in range(N)]
D=0
U=[]
def f(U):
  d=((U[0][0]-U[1][0])**2+(U[0][1]-U[1][1])**2)**0.5
  return d

#print(T)
for i in list(itertools.permutations(range(1,N+1))):
  for j in range(1,N):
    U+=[T[i[j-1]-1],T[i[j]-1]]
#    print('U:',U)
    D+=f(U)
#    print('D:',D)
    U=[]
print(D/math.factorial(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())

s = 0.0
for i in range(n-1):
    for j in range(i+1, n):
        s += math.sqrt((x[i]-x[j])**2+(y[i]-y[j])**2)
        #print("i:", i,"j:", j, "s:", s)

print(2*s/n)

Submission status: Accepted

Solution code:
import math

N = int(input())
xy = []
N_root = math.factorial(N)
distance = 0

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

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

distance *= 2 * math.factorial(N-1)

print(distance/N_root)

Submission status: Accepted

Solution code:
import itertools
import math

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

s = 0
for _p in itertools.permutations(xy, n):
    for i in range(0, n-1):
        s += math.sqrt((_p[i][0]-_p[i+1][0])**2 + (_p[i][1]-_p[i+1][1])**2)

print(s/math.factorial(n))

Submission status: Accepted

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

ans = 0.0
for i in range(n):
  for j in range(n):
    if i == j: continue
    ans += ((a[i][0]-a[j][0]) ** 2 + (a[i][1]-a[j][1]) ** 2) ** 0.5
ans = ans / 2

ans = 2/n *ans
print(ans)

Submission status: Accepted

Solution code:
import itertools

def powpow(xl,yl):
    tmp = pow(xl[0]-yl[0], 2) + pow(xl[1]-yl[1], 2)
    dist = pow(tmp, 0.5)
    return dist


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

    sum = 0

    ls = []
    for i in range(n):
        ls.append(i+1)

    p_list = list(itertools.permutations(ls, n))

    for i in range(len(p_list)):
        for j in range(n-1):
            xl = num_list[p_list[i][j] - 1]
            yl = num_list[p_list[i][j+1] - 1]
            sum += powpow(xl,yl)

    print(sum/len(p_list))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
N = int(input())
XY = tuple(tuple(map(int, input().split())) for _ in range(N))
kumi = tuple(itertools.permutations(XY, N))
ans = 0
def f(xi, yi, xj, yj):
    return ((xi - xj) ** 2 + (yi - yj) ** 2) ** 0.5

for i in kumi:
    for j in range(N-1):
        xi, yi = i[j]
        xj, yj = i[j+1]
        ans += f(xi, yi, xj, yj)
print(ans/len(kumi))

Submission status: Accepted

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

def length(a, b):
  return ((X[a]-X[b])**2 + (Y[a]-Y[b])**2)**0.5
def total_len(L):
  n = len(L)
  total = 0
  for i in range(n-1):
    total += length(L[i], L[i+1])
  return total

from itertools import permutations as prm
import math
s = 0
for i in prm(list(range(0, n)), n):
  s += total_len(i)
print(s / math.factorial(n))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

n = int(input())
D = list()
for _ in range(n):
    D.append(list(map(int,input().split())))
#全探索
sum_d = 0
cnt = 0
for i in range(n):
    for j in range(n):
        xx = math.sqrt((D[i][0]-D[j][0])**2+(D[i][1]-D[j][1])**2)
        sum_d += xx
        cnt += 1
print(sum_d/n)

Submission status: Accepted

Solution code:
import math

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

total_distance = 0
count = 0

for i in range(n):
    for j in range(n):
        if i != j:
            total_distance += math.sqrt( (xy[i][0] - xy[j][0])**2 + (xy[i][1] - xy[j][1])**2 )
            count += 1

print(total_distance / n)

Submission status: Accepted

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

import itertools
ans = 0
def kaijou(n):
    if n==1:
        return 1
    else:
        return n*kaijou(n-1)


for v in itertools.permutations(L, N):
    for i in range(N-1):
        ans += ((XY[v[i]][0]-XY[v[i+1]][0])**2 + (XY[v[i]][1]-XY[v[i+1]][1])**2)**0.5
ans /= 1.0*kaijou(N)
print(ans)

Submission status: Accepted

Solution code:
xx=[]
yy=[]
n=int(input())
for ii in range(n):
    x,y=map(int,input().split())
    xx.append(x)
    yy.append(y)

dd=0.
for i1 in range(n):
    for i2 in range(n):
        dd=dd+((xx[i1]-xx[i2])**2+(yy[i1]-yy[i2])**2)**(0.5)
avedd=dd/n/(n-1)

dd2=avedd*(n-1)
print(dd2)

Submission status: Accepted

Solution code:
#import pysnooper
#import numpy
#import os,re,sys,operator
#from collections import Counter,deque
#from operator import itemgetter,mul
from itertools import accumulate,combinations,groupby,combinations_with_replacement,permutations
from sys import stdin,setrecursionlimit
#from bisect import bisect_left,bisect_right
#from copy import deepcopy
#import heapq
#import math
#import string
#from time import time
#from functools import lru_cache,reduce
from math import factorial,hypot
#import sys
#from fractions import gcd
setrecursionlimit(10**6)
input=stdin.readline

n=int(input().rstrip())
l=permutations(range(n),n)
dis=[]
d=[list(map(int,input().split())) for _ in range(n)]
now=0
for i in l:
    #print(i)
    for j in range(n-1):
        now+=hypot((d[i[j]][0]-d[i[j+1]][0]),(d[i[j]][1]-d[i[j+1]][1]))
        #print(now)
print(now/factorial(n))

Submission status: Accepted

Solution code:
import itertools
import math
import statistics

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

lengths = []
for pattern in itertools.permutations(range(N)):
    length = 0
    for path in [(pattern[i],pattern[i+1]) for i in range(N-1)]:
        length += math.sqrt((x[path[0]]-x[path[1]])**2 + (y[path[0]]-y[path[1]])**2)
    lengths.append(length)

# 平均
print(statistics.mean(lengths))

Submission status: Accepted

Solution code:
'''input
8
-406 10
512 859
494 362
-955 -475
128 553
-986 -885
763 77
449 310
'''
# A coding delight
from sys import stdin, stdout
import gc
gc.disable()
input = stdin.readline
from itertools import permutations


def compute_distance(index):
	index = list(index)
	dist = 0
	for i in range(1, len(index)):
		x2 = coord[index[i]][0]
		y2 = coord[index[i]][1]
		x1 = coord[index[i - 1]][0]
		y1 = coord[index[i - 1]][1]
		dist += ((x1 - x2) ** 2 + (y1 - y2)**2) ** 0.5
	return dist

# main starts
n = int(input().strip())
coord = []
for _ in range(n):
	x, y = list(map(int, input().split()))
	coord.append([x, y])

index = [x for x in range(n)]
All = permutations(index)
k = 0
dist = 0
for i in All:
	k += 1
	dist += compute_distance(i)
print(dist/k)

Submission status: Accepted

Solution code:
import math
n = int(input())
c = [list(map(int, input().split())) for i in range(n)]
#print(n)
#print(c)
def euc_dist(c1, c2):
  x1, y1 = c1
  x2, y2 = c2
  return round(math.sqrt((x1 - x2)**2 + (y1 - y2)**2), 10)
"""
def dcount(m):
  if m<2: return 0
  elif m==2: return 1
  else: return dcount(m-1) + m-1
  """

d = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
  for j in range(n):
    if i==j: d[i][j] = 0
    else: d[i][j] = euc_dist(c[i], c[j])
#print(d)

sum = 0
for i in range(n):
  for j in range(n):
    #print('sum={}'.format(sum))
    sum += d[i][j]
#print('sum={}, (n-1)!={}, n={}'.format(sum, math.factorial(n-1), n))
print(sum/n)

Submission status: Accepted

Solution code:
from itertools import permutations
from math import factorial


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


N = int(input())

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

res = 0
for perm in permutations(range(N), N):
    for i, j in zip(perm[:N-1], perm[1:]):
        res += distance(xs[i], ys[i], xs[j], ys[j])

print(res/factorial(N))

Submission status: Accepted

Solution code:
import itertools
N = int(input())
xy = [[int(x) for x in input().split()] for i in range(N)]
ans = 0
count = 0
for city in itertools.permutations(xy,2):
  ans += ((city[0][0]-city[1][0])**2 + (city[0][1]-city[1][1])**2)**0.5
  count += 1
print(ans/N)

Submission status: Accepted

Solution code:
import math
N = int(input())
S = []
for i in range(N):
  S.append(list(map(int, input().split())))
def dist(a, b):
  return ((a[0]-b[0])**2 + (a[1]-b[1])**2) ** 0.5
D = [dist(S[i], S[j]) for i in range(N-1) for j in range(i+1, N)]
print (sum(D)*(N-1)/N/(N-1)*2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import sqrt
from itertools import permutations
N = int(input())
roots = permutations(range(N))
points = [[int(i) for i in input().split()] for _ in range(N)]


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


distance_sum = 0
cnt = 0
for root in roots:
    cnt += 1
    _d = 0
    for i in range(1, N):
        prev = root[i-1]
        current = root[i]
        _d += calc_distance(points[prev], points[current])
    distance_sum += _d
print(distance_sum / cnt)

Submission status: Accepted

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

length_list = []
for i in range(N-1):
    for j in range(i+1, N):
        l = math.sqrt((array[i][0] - array[j][0])**2 + (array[i][1] - array[j][1])**2)
        length_list.append(l)

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