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 math
n=int(input())
a=[]
for _ in range(n):
    a.append(list(map(int,input().split())))
s=0
for i in range(n):
    for j in range(n):
        if j!=i:
            s+=((a[i][0]-a[j][0])**2+(a[i][1]-a[j][1])**2)**0.5
print((n-1)*s/(n*(n-1)))

Submission status: Accepted

Solution code:
from math import sqrt, factorial
n = int(input())
x, y = [0] *  n, [0] * n

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

total = 0
for i in range(n):
    for j in range(i + 1, n):
        #print(sqrt((x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2))
        total += 2 * sqrt((x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2)

print(total / n)

Submission status: Accepted

Solution code:
from math import sqrt, factorial
n = int(input())
x, y = [0] *  n, [0] * n

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

total = 0
for i in range(n):
    for j in range(n):
        total += sqrt((x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2)

print(total / n)

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
# https://atcoder.jp/contests/abc145/tasks/abc145_c

def solve():
    import math
    from math import factorial
    import itertools

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

    def calc(b, a):
        bc, ac = cities[b], cities[a]
        return math.sqrt((bc[0]-ac[0])**2 + (bc[1]-ac[1])**2)

    perms = itertools.permutations([i for i in range(N)], r=N)
    total = 0
    for perm in perms:  # 8! = 40320
        a = perm[0]
        for i in range(1, N):  # 8
            b = perm[i]
            total += calc(b, a)
            a = b
    print(total/factorial(N))


def solve2():
    # TLE
    import copy
    import math
    from math import factorial

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

    def calc(visit):
        d = 0
        a = cities[visit[0]]
        for i in range(1, N):
            b = cities[visit[i]]
            d += math.sqrt((b[0]-a[0])**2 + (b[1]-a[1])**2)
            a = b
        return d

    def rec(visit, visit_set, rest):
        if len(visit) == N:
            return calc(visit)

        total = 0
        for i in rest:
            tmp_visit = copy.deepcopy(visit)
            tmp_visit_set = copy.deepcopy(visit_set)
            tmp_rest = copy.deepcopy(rest)

            if i in tmp_visit_set:
                continue
            tmp_visit.append(i)
            tmp_visit_set.add(i)
            tmp_rest.remove(i)

            total += rec(tmp_visit, tmp_visit_set, tmp_rest)
        return total

    d = rec([], set(), set([i for i in range(N)]))
    print(d/factorial(N))


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces


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


def main():
    n = ni()
    points = []
    ave1path = 0
    for _ in range(n):
        points += [na()]
    for i in range(n-1):
        for j in range(i+1,n):
            ave1path += distance(points[i], points[j])
    print(ave1path*2 / n)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

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

x = math.factorial(n)
y = (n-1)*(n)/2
z = x*(n-1)/y

sum_dis = 0
for i in range(n-1):
    xi = s[i][0]
    yi = s[i][1]
    for j in range(i+1,n):    
        xj = s[j][0]
        yj = s[j][1]
        dis = math.sqrt(math.pow((xi-xj),2) + math.pow((yi - yj),2))
        sum_dis += z*dis

print(sum_dis/x)

Submission status: Accepted

Solution code:
from math import sqrt
def d(x1,x2,y1,y2):
	return sqrt((x2-x1)**2+(y2-y1)**2)
	
n=int(input())
res=0
Z=[]
for i in range(n):
	xy = list(map(int,input().split()))
	Z.append(xy)
for i in range(n):
	for j in range(i+1,n):
		res += d(Z[i][0],Z[j][0],Z[i][1],Z[j][1])
print(res*2/n)

Submission status: Accepted

Solution code:
# 12:03
import itertools
import math
n = int(input())

cities = [list(map(int, input().split())) for _ in range(n)]
a=[]
for i in range(n):
    a.append(i)
a = list(itertools.permutations(a))
sum = 0
for city in a:
    for i in range(n-1):
        sum += ((cities[city[i+1]][0]-cities[city[i]][0])**2 +
                (cities[city[i+1]][1]-cities[city[i]][1])**2)**0.5
print(sum/math.factorial(n))

Submission status: Accepted

Solution code:
import math
import itertools

N = int(input())

renban = list(range(N))
michi = list(itertools.combinations(renban, 2))
arr = [list(map(int, input().split())) for _ in range(N)]
kyori_list =[]

for i in range(len(michi)):
    kyori = math.sqrt((arr[michi[i][0]][0]-arr[michi[i][1]][0])**2+(arr[michi[i][0]][1]-arr[michi[i][1]][1])**2)
    kyori_list.append(kyori)

print(sum(kyori_list)*(N-1)/len(michi))

Submission status: Accepted

Solution code:
import itertools
import math

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

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

N = int(input())

pos_dict = {i: list(map(int, input().split())) for i in range(1, N + 1)}

sum_distance = 0
for p in itertools.permutations(range(1, N + 1)):
  for i in range(len(p) - 1):
    sum_distance += calc_distance(pos_dict[p[i]], pos_dict[p[i+1]])

print(sum_distance / permutations_count(N, N))

Submission status: Accepted

Solution code:
import sys
import itertools
import math

readline = sys.stdin.readline
sqrt = math.sqrt

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


def main():
    N = int(input())
    G = []
    for _ in range(N):
        G.append(list(map(int, readline().split())))
    
    permN = itertools.permutations(range(N))
    d = []
    for p in permN:
        tmp = 0
        for i in range(len(p)-1):
            a = p[i]; b = p[i+1]
            tmp += distance(G[a], G[b])
        d.append(tmp)
    ans = sum(d)/len(d)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools
import math
N = int(input())
ll = list()
for n in range(N):
    l = list(map(int, input().split()))
    ll.append(l)
p = list()
for i in range(N):
    p.append(i)
p = itertools.permutations(p)
total = 0
for i in p:
    for s in range(len(i) - 1):
        total += math.sqrt((ll[i[s]][0]-ll[i[s+1]][0])**2 + (ll[i[s]][1]-ll[i[s+1]][1])**2)
print(total/float(math.factorial(N)))

Submission status: Accepted

Solution code:
n = int(input())
xyies = [list(map(int,input().split())) for _ in range(n)]
wa = 0
#まず全ての順列を生成します
import itertools
import math
l = [i for i in range(n)]
p = itertools.permutations(l,n)
#距離の和を求めます
for v in p:
    for i in range(n-1):#n個の町の間はn-1個なので
        start = xyies[v[i]]#スタートの座標
        goal = xyies[v[i+1]]#ゴールの座標
        distance_from_i = ((start[0]-goal[0])**2 + (start[1]-goal[1])**2)**(1/2)
        wa += distance_from_i
waa = math.factorial(n)
print(wa/waa)

Submission status: Accepted

Solution code:
import itertools
from math import sqrt
N=int(input())

def distance(x1,y1,x2,y2):
    return sqrt( (x2-x1)**2+(y2-y1)**2)
L=[]
for i in range(N):
    x,y=map(int, input().split())
    L.append((x,y))

ans=0
count=0
for T in itertools.permutations(L):
    
    for i,t in enumerate(T):
        if i==0:
            prex,prey=t
            continue
        x,y=t
        ans+=distance(prex,prey,x,y)
        prex=x
        prey=y
    count+=1

print(ans/count)

Submission status: Accepted

Solution code:
from itertools import permutations
from math import factorial

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

dists = [[0] * N for _ in range(N)]
for i in range(N):
    for j in range(i + 1, N):
        dists[i][j] = dists[j][i] = (
            (cities[j][0] - cities[i][0]) ** 2 + (cities[j][1] - cities[i][1]) ** 2
        ) ** 0.5

total_dist = 0
for p in permutations(range(N)):
    for i in range(N - 1):
        total_dist += dists[p[i]][p[i + 1]]

print(total_dist / factorial(N))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import itertools

def distance(x0, y0, x1, y1):
    d = math.sqrt((x0 - x1)**2 + (y0 - y1)**2)
    return d

N = int(input())
xy = [map(int, input().split()) for _ in range(N)]
x, y = [list(i) for i in zip(*xy)]
#print("x" + str(x))
#print("y" + str(y))

n = [int(x) for x in range(N)]
itr = list(itertools.permutations(n))
#print("n" + str(itr))

d = 0

for c in itr:
#    print("=================================================")
#    print(c)
    
    for i in range(N - 1):
#        print("------------------------------------")
#        print("i:" + str(i))
#        a = x[c[i]]
#        print("a:" + str(a))
        d += distance(x[c[i]], y[c[i]], x[c[i+1]], y[c[i+1]])
ans = d/len(itr)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=[[int(i) for i in input().split()] for l in range(n)]
c=0
for x in s:
    for y in s:
        c+=((x[0]-y[0])**2+(x[1]-y[1])**2)**0.5
print(c/n)

Submission status: Accepted

Solution code:
import itertools
import math

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

ans=0.0
fact=1
for i in range(2,N+1):
    fact*=i

ans=0.0
v=[]
for i in range(N):
    v.append(i)

for s in itertools.permutations(v):
    for j in range(N-1):
        ans+=math.sqrt((XY[s[j]][0]-XY[s[j+1]][0])**2+(XY[s[j]][1]-XY[s[j+1]][1])**2)

print(ans/fact)

Submission status: Accepted

Solution code:
from itertools import permutations as perms

n = int(input().strip())
xys = [tuple(map(int, input().split())) for _ in range(n)]
lis = [i for i in range(n)]

numerator = 0
denominator = 0
for elem in perms(lis, n):
    denominator += 1
    for i in range(len(elem) - 1):
        numerator += ((xys[elem[i + 1]][0] - xys[elem[i]][0]) ** 2 + (xys[elem[i + 1]][1] - xys[elem[i]][1]) ** 2) ** (1 / 2)
print(numerator / denominator)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
import math

N = 3
ARR = [
    [0, 0],
    [1, 0],
    [0, 1]
]


N = 2
ARR = [
    [-879, 981],
    [-866, 890],
]


N = 8
ARR = [
    [-406, 10],
    [512, 859],
    [494, 362],
    [-955, -475],
    [128, 553],
    [-986, -885],
    [763, 77],
    [449, 310]
]

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

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



def calculate(n, arr):
    result = 0
    s = 0
    for comb in itertools.permutations(range(n), n):
        s = s + 1
        comb = list(comb)
        d = 0
        for index in range(n - 1):
            d = d + distance(arr[comb[index]][0], arr[comb[index]][1], arr[comb[index+1]][0], arr[comb[index+1]][1])

        result = result + d

    print(result / s)


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


calculate(N, ARR)

Submission status: Accepted

Solution code:
import math
n=int(input())
m = [list(map(int, input().split())) for _ in range(n)]
ans=0

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

Submission status: Accepted

Solution code:
import itertools
import math
def main():
    N = int(input())
    pos = list()
    for i in range(N):
        x, y = map(int, input().split())
        pos.append([x, y])

    l = [i for i in range(0, N)]
    dist = 0
    for c in itertools.permutations(l, N):
        for i in range(len(c) - 1):
            dist += math.sqrt( (pos[c[i]][0] - pos[c[i+1]][0])**2 +  (pos[c[i]][1] - pos[c[i+1]][1])**2 )

    print(dist/float(math.factorial(N)))
if __name__ == "__main__":
    main()

Submission status: Accepted

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


def solve(N: int, x: "List[int]", y: "List[int]"):
    seq = range(N)
    comb = math.factorial(N)
    all_distance = 0.0
    for road_map in itertools.permutations(seq):
        for n in range(N - 1):
            n1 = road_map[n]
            n2 = road_map[n+1]
            all_distance += math.sqrt(pow(x[n1] - x[n2],
                                          2) + pow(y[n1] - y[n2], 2))
    print(all_distance / comb)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def solve(N: int, x: "List[int]", y: "List[int]"):
    seq = range(N)
    comb = math.factorial(N)
    all_distance = [float(0.0)] * comb
    for i, road_map in enumerate(itertools.permutations(seq)):
        for n in range(N - 1):
            n1 = road_map[n]
            n2 = road_map[n+1]
            all_distance[i] += math.sqrt(pow(x[n1] - x[n2],
                                             2) + pow(y[n1] - y[n2], 2))
    print(sum(all_distance) / comb)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

import math
sm = 0
for i in range(n):
    for j in range(i+1, n):
        sm += math.sqrt((S[i][0] - S[j][0])**2 + (S[i][1] - S[j][1])**2)
ans = sm*2/n
print(ans)

Submission status: Accepted

Solution code:
def main():
    import itertools
    n = int(input())
    spot = []
    for i in range(n):
        x,y = map(int,input().split())
        spot.append([x,y])
    s = 0
    cnt = 0
    for i in itertools.permutations([i for i in range(n)]):
        cnt += 1
        for j in range(len(i)-1):
            s += ((spot[i[j+1]][0]-spot[i[j]][0])**2+(spot[i[j+1]][1]-spot[i[j]][1])**2)**0.5
    print(s/cnt)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=[]
ans=0
ANS=0
A=0
import itertools
for i in range(n):
    x,y=map(int,input().split())
    a.append([x,y])
for v in itertools.permutations(a, n):
    A+=1
    for i in range(n-1):
        ans+=((list(v)[i][0]-list(v)[i+1][0])**2+(list(v)[i][1]-list(v)[i+1][1])**2)**0.5
print(ans/A)

Submission status: Accepted

Solution code:
import math
import itertools
N = int(input())
P = []
S = math.factorial(N)
T = []
for i in range(N):
  x,y = (int(x) for x in input().split())
  T.append(i)
  P.append((x,y))
c = list(itertools.combinations(T, 2))
sum = 0
for i in c:
  sum += ((P[i[0]][0] - P[i[1]][0])**2 + (P[i[0]][1] - P[i[1]][1])**2)**(1/2)
print(sum*(math.factorial(N-1))*2/S)

Submission status: Accepted

Solution code:
import sys
import math
from collections import Counter
import itertools
#from functools import reduce

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'

# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")

# ###########################################

N=II()
L=LLI(N)

itr = list(itertools.permutations(L))

su=0
for i in itr:
    for x in range(0, N-1):
        su+=math.sqrt((i[x][0]-i[x+1][0])**2 + (i[x][1]-i[x+1][1])**2)
print(su/len(itr))

Submission status: Accepted

Solution code:
import itertools as iter
import math
N = int(input())
N_list =[i for i in range(N)]
C = [list(map(int,input().split())) for i in range(N)]
per = iter.permutations(N_list)
T = 0
for v in per:
    for i in range(len(v)-1):
      T += ((C[v[i+1]][0] - C[v[i]][0])**2 + (C[v[i+1]][1] - C[v[i]][1])**2)**0.5
print(T/math.factorial(N))

Submission status: Accepted

Solution code:
from itertools import combinations

def dist(i,j):
    return ((i[0]-j[0])**2+(i[1]-j[1])**2)**0.5
    
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
l=combinations(range(0,n),2)

res=[dist(xy[i],xy[j]) for i,j in l]

print(2*sum(res)/n)

Submission status: Accepted

Solution code:
from itertools import permutations, combinations,combinations_with_replacement,product
import sys
input = sys.stdin.readline
import math

n = int(input())
town = []
for i in range(n):
    town.append(list(map(int, input().replace("\n","").split())))
townnum = [i for i in range(n)]

chklist = list(permutations(townnum))

sumval = 0.0
for i in range(len(chklist)):
    for j in range(n-1):
        sumval += math.sqrt(((town[chklist[i][j]][0] - town[chklist[i][j+1]][0])**2) + ((town[chklist[i][j]][1] - town[chklist[i][j+1]][1])**2))

print(sumval/len(chklist))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
import math

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

all_total_rl = []
for route in itertools.permutations(xylis,N):
    total_rl = 0
    for i in range(N-1):
        nakami = (route[i][0]-route[i+1][0])**2 + (route[i][1]-route[i+1][1])**2
        route_length = math.sqrt(nakami)
        total_rl += route_length
    all_total_rl.append(total_rl)

ans = sum(all_total_rl) / len(all_total_rl)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

from math import sqrt
def dist(x1, y1, x2, y2):
    return sqrt((x1-x2)**2 + (y1-y2)**2)
xx = []
yy = []
for i in range(n):
    x, y = map(int, input().split())
    xx += [x]
    yy += [y]

dists = [dist(xx[i], yy[i], xx[j], yy[j]) for i in range(n) for j in range(i+1,n)]      
print((n-1) * sum(dists) / len(dists))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# 20/4/25 Use combinations
import math
N = int(input())
x = [0] * N
y = [0] * N
for i in range(N):
    x[i], y[i] = [int(x) for x in input().split()]

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

# (sum_d / NC2) * (N - 1)
print(2 * sum_d / N)

Submission status: Accepted

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

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

# (sum_d / NC2) * (N - 1)
print(2 * sum_d / N)

Submission status: Accepted

Solution code:
from itertools import permutations

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

listP = list(permutations(range(N), N))
sum_d = 0
for p in listP:
    for i in range(1, N):
        sum_d += ((x[p[i]] - x[p[i - 1]]) ** 2 + (y[p[i]] - y[p[i - 1]]) ** 2) ** 0.5

print(sum_d / len(listP))

Submission status: Accepted

Solution code:
import math
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    POS = [list(map(int, input().split())) for i in range(N)]
    DIS = [[0]*(N) for _ in range(N)]
    M = 1
    for i in range(1,N+1):
        M *= i
    for i in range(N):
        for j in range(N):
            DIS[i][j] = math.sqrt((POS[i][0] - POS[j][0])**2 +(POS[i][1] - POS[j][1])**2)
    print(sum(map(sum, DIS))/N)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

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

length = []
for i in range(N):
    x_1 = xy[i][0]
    y_1 = xy[i][1]
    for j in range(i + 1, N):
        x_2 = xy[j][0]
        y_2 = xy[j][1]
        lon = math.sqrt((x_1 - x_2) ** 2 + (y_1 - y_2) ** 2)
        length.append(lon)

result = (N - 1) * sum(length) / len(length)
print(result)

Submission status: Accepted

Solution code:
import itertools
import math

n = int(input())
lis = [j for j in range(n)]
points = []

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

def distance(forw, back):
  #print(points[forw][0])
  return math.sqrt((points[forw][0]-points[back][0])**2+(points[forw][1]-points[back][1])**2)

sum_,k = 0,0
for one_case in permutations_lis:
  k+=1
  for j in range(len(one_case)-1):
    dis = distance(one_case[j],one_case[j+1])
    sum_+=dis
print(sum_/k)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from itertools import permutations
n = int(input())
C = [[0, 0] for i in range(n)]    #Coordinate

for i in range(n):
    xi, yi = map(int, input().split())
    C[i][0], C[i][1] = xi, yi

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

ans = 0
R = list(permutations(C))
for V in R:
    tmp = 0
    for i in range(len(V)-1):
        tmp += dis(V[i][0], V[i][1], V[i+1][0], V[i+1][1])
    ans += tmp/len(R)

print(ans)

Submission status: Accepted

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


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


dis_sum = 0
for i in range(math.factorial(n)):
    for j in range(n-1):
        dis_sum += distance(xy[junnretu[i][j]], xy[junnretu[i][j+1]])


ans = dis_sum / math.factorial(n)
print(ans)

Submission status: Accepted

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))

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

Submission status: Accepted

Solution code:
def permutation(n,x,mod=10**9+7):
    tmp=1
    for i in range(n,n-x,-1):
        tmp=(tmp*i)%mod
    return tmp

import itertools
n=int(input())
lst=[list(map(int,input().split())) for _ in range(n)]
patlen=permutation(n,n)
patlst=list(itertools.permutations(lst,n))
kyori=0
for i in patlst:
    for j in range(n-1):
        kyori+=((i[j][0]-i[j+1][0])**2+(i[j][1]-i[j+1][1])**2)**0.5
        
print(kyori/patlen)

Submission status: Accepted

Solution code:
from itertools import permutations
import math
n = int(input())
l = [list(map(int,input().split())) for _ in range(n)]
num = list(range(n))
su = 0
for i in permutations(num):
  for j in range(n-1):
    a = i[j]
    b = i[j+1]
    su += ((l[a][0]-l[b][0])**2+(l[a][1]-l[b][1])**2)**0.5
print(su/math.factorial(n))

Submission status: Accepted

Solution code:
import math
import itertools

n=int(input())

d={}
for i in range(n):
    d[i] = tuple(map(int,input().split()))

def calc(a,b):

    x,y = d[a] 
    xx,yy = d[b]

    return math.sqrt((x-xx)**2 + (y-yy)**2)

res=0
for i in itertools.permutations(range(n)):


    for  j in range(n-1):
        res+= calc(i[j],i[j+1])


print(res/math.factorial(n))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import combinations


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


n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
l = combinations([i for i in range(n)], 2)
length = [dist(xy[i], xy[j]) for i, j in l]

print(2*sum(length)/n)

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt, pow, factorial

def length(a, b):
    x1, y1 = a
    x2, y2 = b
    return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2))

N = int(input())
xy = []
for i in range(N):
    xy.append(list(map(int, input().split())))
    
ans = 0
for order in permutations(range(N)): # 経路全探索
    tmp = 0
    for i in range(1, N):
        tmp += length(xy[order[i]], xy[order[i - 1]])
    ans += tmp
    
ans /= factorial(N)
print(ans)

Submission status: Accepted

Solution code:
from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
from itertools import permutations
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

N = I()

def distance(x,y):
    return (x - y)**2

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

l = list(permutations(ls))

ans =0
for js in l:
    for j in range(len(js)-1):
        ans += sqrt(distance(js[j][0],js[j+1][0]) + distance(js[j][1],js[j+1][1]))

print(ans/len(l))

Submission status: Accepted

Solution code:
def dist(p,q):
  return sum((px - qx) ** 2.0 for px, qx in zip(p, q))**0.5
n=int(input())
p=[]
for _ in range(n):
  p.append(list(map(int,input().split())))
import itertools
a=list(itertools.permutations(range(n)))
ans=[]
for i in a:
  d=0
  for j in range(n-1):
    d+=dist(p[i[j]],p[i[j+1]])
  ans.append(d)
from statistics import mean
print(mean(ans))

Submission status: Accepted

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

l=[i for i in range(N)]
kai=N
for i in range(1,N):
  kai *= i

p = itertools.permutations(l, N)

def d(xi,xj,yi,yj):
  a=((xi - xj)**2 + (yi - yj)**2)**(1/2)
  return a

ds=0
for i in p:
  for j in range(1,N):
    ds += d(xy[i[j-1]][0],xy[i[j]][0],xy[i[j-1]][1],xy[i[j]][1])

print(ds/kai)

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())
    
result = 0

for i in range(n):
    for j in range(i, n):
        result += ((x[i] - x[j])**2 + (y[i] - y[j])**2)**(0.5)
        
print(result*2/n)