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:
# -*- coding: utf-8 -*-

import sys
from math import hypot

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
XY = []
for i in range(N):
    x, y = MAP()
    XY.append((x, y))

dist = 0
for i in range(N):
    x, y = XY[i]
    for j in range(i+1):
        x2, y2 = XY[j]
        dist += hypot(x-x2, y-y2)
print(dist * 2 / N)

Submission status: Accepted

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

def solve(ite):
	a = 0
	for i in range(len(ite)-1):
		a += ((x[ite[i]] - x[ite[i+1]])**2 + (y[ite[i]] - y[ite[i+1]])**2) ** (1/2)
	return a


def next_permutation(n, flg, perm):
	S = []
	if flg.count(0) == 0:
		return solve(perm)

	a = 0
	for i in range(n):
		if flg[i] != 0:
			continue

		flg[i] = 1
		perm.append(i)

		a += next_permutation(n, flg, perm)

		flg[i] = 0
		perm.pop()

	return a


flg = [0] * N
perm = []

A = next_permutation(N,flg,perm)

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

print(A)

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

import itertools
import math


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

Sum_N = 0

for i in range(len(p)):

    Sum = 0

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

    Sum_N += Sum

print(Sum_N / len(p))

Submission status: Accepted

Solution code:
import math
import numpy as np
import itertools
N = int(input())
x = []; y= []
for _ in range(N):
    x_,y_ = map(int,input().split())
    x.append(x_)
    y.append(y_)
lis = np.zeros((8,8))
for i in range(N):
    for j in range(N):
        lis[i,j] = math.sqrt((x[i]-x[j])**2 + (y[i]-y[j])**2)
num = 0
su = 0
ite = itertools.permutations([i for i in range(N)])
for it in ite:
    for i in range(len(it)-1):
        su += lis[it[i],it[i+1]]
    num += 1
print(su/num)

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
import copy
from math import factorial

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

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

    memo = {}  # 距離の事前計算
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            memo[(i,j)] = calc_distance(cities[i], cities[j])

    degree = N-1  # 頂点の次数
    coef = factorial(degree)

    ans = 0
    for key, value in memo.items():
        ans += value * coef * 2  # 経路(1,2)と経路(2,1)で倍にする必要がある
    ans = ans / factorial(N)
    print(ans)


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

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

    memo = {}  # 距離の事前計算
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            memo[(i,j)] = calc_distance(cities[i], cities[j])

    def dfs(will_visit, visited, now_i, total_d):
        if now_i is None:
            ans = 0
            for i in will_visit:
                new_will_visit = copy.deepcopy(will_visit)
                new_visited = copy.deepcopy(visited)
                new_will_visit.remove(i)
                new_visited.add(i)
                ans += dfs(new_will_visit, new_visited, i, 0)
            return ans

        if will_visit == []:
            return total_d

        ans = 0
        for i in will_visit:
            if i in visited: continue
            new_will_visit = copy.deepcopy(will_visit)
            new_visited = copy.deepcopy(visited)
            new_will_visit.remove(i)
            new_visited.add(i)
            ans += dfs(new_will_visit, new_visited, i, total_d+memo[min(now_i, i), max(now_i, i)])
        return ans

    will_visit = [i for i in range(1, N+1)]
    visited = set()
    ans = dfs(will_visit, visited, None, 0)
    print(ans/factorial(N))


if __name__ == "__main__":
    solve2()

Submission status: Accepted

Solution code:
import itertools
import numpy as np
def dist(p1,p2):
    dx = p1[0] - p2[0]
    dy = p1[1] - p2[1]
    return (dx ** 2 + dy ** 2)**0.5
    
ans = 0
n = int(input())
lis = []
for _ in range(n):
  x, y = map(int, input().split())
  lis.append((x, y))
per = list(itertools.permutations(lis, n))
count = 0
for i in per:
    for j in range(1,n):
        ans += dist(i[j-1],i[j])
print(ans/len(per))

Submission status: Accepted

Solution code:
import math
import itertools

n = int(input())
route = list(range(n))

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

distance = 0
for r in itertools.permutations(route):
    for i in range(n-1):
        distance += math.sqrt((town[r[i]][0] - town[r[i+1]][0])
                              ** 2 + (town[r[i]][1] - town[r[i+1]][1])**2)

print(distance/math.factorial(n))

Submission status: Accepted

Solution code:
def dist(x1, x2):
    d = (x1[0] - x2[0])**2 + (x1[1] - x2[1])**2
    return d**0.5

n = int(input())
x = [list(map(int, input().split())) for _ in range(n)]
d = 0
for i in range(n-1):
    for j in range(i+1, n):
        d += dist(x[i], x[j])
print(2*d / n)

Submission status: Accepted

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

pos = []

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

routes= list(itertools.permutations(pos, n))

sum = 0
for r in routes:
  for i in range(1, n):
    d = ((r[i][0] - r[i-1][0]) ** 2) + ((r[i][1] - r[i-1][1]) ** 2)
    sum += math.sqrt(d)

print(sum/len(routes))

Submission status: Accepted

Solution code:
def dist(x1, x2):
    d = (x1[0] - x2[0])**2 + (x1[1] - x2[1])**2
    return d**0.5

n = int(input())
x = [list(map(int, input().split())) for _ in range(n)]
d = 0
for i in range(n-1):
    for j in range(i+1, n):
        d += dist(x[i], x[j])
print(2*d / n)

Submission status: Accepted

Solution code:
import itertools
import math

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

ans = 0
for perm in itertools.permutations([i for i in range(N)]):
    for i in range(N - 1):
        ans += ((P[perm[i]][0] - P[perm[i+1]][0]) ** 2
                + (P[perm[i]][1] - P[perm[i+1]][1]) ** 2) ** 0.5

print(ans / math.factorial(N))

Submission status: Accepted

Solution code:
from math import sqrt
n=int(input())
x=[0]
y=[0]
k=1
s=0
m=2
for i in range(1,n+1):
    a,b=map(int,input().split())
    x.append(a)
    y.append(b)
    k*=i
    m*=i
m//=n
for i in range(1,n+1):
    for j in range(i+1,n+1):
        s+=sqrt((x[i]-x[j])**2+(y[i]-y[j])**2)*m
v=round(s/k,10)
print(v)

Submission status: Accepted

Solution code:
def dist(x1, x2):
    d2 = (x1[0] - x2[0]) ** 2 + (x1[1] - x2[1]) ** 2
    return d2 ** 0.5

n = int(input())
x = [list(map(int, input().split())) for _ in range(n)]
d = 0
for i in range(n - 1):
    xi = x[i]
    for j in range(i + 1, n):
        d += dist(xi, x[j])
print(2 * d / n)

Submission status: Accepted

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

coord = list()
for _ in range(N):
    c = tuple(map(int, input().split()))
    coord.append(c)

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

perm = 0
for i, p1 in enumerate(coord):
        for p2 in coord[i+1:]:
            d = calc_dist(p1, p2)
            perm += 2*d/N

print(perm)

Submission status: Accepted

Solution code:
import math
import itertools

n = int(input())

fac = math.factorial(n)

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

# print(fac)
# print(p)
# print()

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

term = 0
for c in list(itertools.permutations(p)):
    t = 0
    for i in range(len(c)-1):
        t += math.sqrt((c[i][0] - c[i+1][0]) ** 2 + (c[i][1] - c[i+1][1]) ** 2)
        # print("x=%d y=%d and x=%d y=%d" % (c[i][0], c[i][1], c[i+1][0], c[i+1][1]))
        # print(t)
    term += t
    # print(term)
print(term / fac)

Submission status: Accepted

Solution code:
import math
import itertools
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
rt=[]
for i in range(n):
    for j in range(i+1,n):
        x1=xy[i][0]
        y1=xy[i][1]
        x2=xy[j][0]
        y2=xy[j][1]
        rt.append([(i,j),math.sqrt((x1-x2)**2+(y1-y2)**2)])
l=[i for i in range(n)]
sm=0
cnt=0
for v in list(itertools.permutations(l,n)):
    for i in range(n-1):
        f,t=v[i],v[i+1]
        if f>t:
            f,t=t,f
        for r in rt:
            if r[0]==(f,t):
                sm+=r[1]
    cnt+=1
print(sm/cnt)

Submission status: Accepted

Solution code:
import itertools
import math
n = int(input())
towns = []
s = 0
s_list = []
for i in range(n):
    towns.append([int(a) for a in input().split(' ')])
    s_list.append(str(i))
ps = [''.join(p) for p in itertools.permutations(s_list)]

k = 0
for i, p in enumerate(ps):
    p = list(p)  # ['0', '1', '2']
    for j in range(len(p)):
        if j+1 >= n:  # n = 3
            break
        s += math.sqrt(((towns[int(p[j])][0] - towns[int(p[j+1])][0])**2) + ((towns[int(p[j])][1] - towns[int(p[j+1])][1])**2))
    k += 1

print(s / k)

Submission status: Accepted

Solution code:
from itertools import permutations
from math import hypot, factorial
N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
 
total = 0
for p in permutations(a):
    for i in range(N-1):
        total += hypot(p[i][0]-p[i+1][0], p[i][1]-p[i+1][1])
    
print(total / factorial(N))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import Counter, deque, defaultdict, OrderedDict
from math import factorial
from fractions import Fraction
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n = INT()
x = [0]*n
y = [0]*n
res = 0
for i in range(n):
    xx, yy = MAP()
    x[i] = xx
    y[i] = yy
dist = [[0]*n for i in range(n)]
for i in range(n):
    for j in range(n):
        dist[i][j] = math.sqrt((x[i]-x[j])**2 + (y[i]-y[j])**2)

p_list = list(itertools.permutations([i for i in range(n)], n))
for per in p_list:
    temp = list(per)
    for i in range(n-1):
        res += dist[temp[i]-1][temp[i+1]-1]

print(res/len(p_list))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc145/tasks/abc145_c

import sys
sys.setrecursionlimit(12345678)
import itertools
import math
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def main():
    n = int(input())
    nl = [i for i in range(n)]

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

    total = 0
    routes = list(itertools.permutations(nl))
    for route in routes:
        # print(route)
        distance = 0
        for i in range(1, len(route)):
            src_x = xy[route[i-1]][0]
            src_y = xy[route[i-1]][1]
            dst_x = xy[route[i]][0]
            dst_y = xy[route[i]][1]
            distance += math.sqrt((dst_x - src_x) * (dst_x - src_x) + (dst_y - src_y) * (dst_y - src_y))

        total += distance
    # print(len(routes))
    print(total / len(routes))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
n = int(input())
A = []
sum = 0
for i in range(n) :
  a,s = (int(x) for x in input().split())
  A.append((a,s))
for i in A:
  for i2 in A:
    sum+=math.sqrt((i[0]-i2[0])**2+(i[1]-i2[1])**2)
print(sum/n)

Submission status: Accepted

Solution code:
import math
N=int(input())
Z=[]*N
for i in range(N):
    A=list(map(int,input().split()))
    Z.append(A)
def D(x1,x2,y1,y2):
    return pow((x1-x2)**2+(y1-y2)**2,0.5)

ans=0
for i in range(N):
    for j in range(i,N):
        ans+=D(Z[i][0],Z[j][0],Z[i][1],Z[j][1])*math.factorial(N-1)*2
print(ans/math.factorial(N))

Submission status: Accepted

Solution code:
from itertools import permutations
import math

N = int(input())
V = [tuple(map(int, input().split())) for _ in range(N)]
ans = 0
for indices in permutations(range(N)):
    for i in range(N - 1):
        j = indices[i]
        k = indices[i + 1]
        ans += math.sqrt((V[j][0] - V[k][0]) ** 2 + (V[j][1] - V[k][1]) ** 2)
ans /= math.factorial(N)
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math

if __name__ == "__main__":
  N = int(input())
  
  points = []
  
  for _ in range(N):
    points.append(list(map(int, input().split())))
    
  sum_dist = 0

  for ord_ps in itertools.permutations(points, N):
    for i in range(N - 1):
      sum_dist += math.sqrt((ord_ps[i][0] - ord_ps[i + 1][0]) ** 2 + (ord_ps[i][1] - ord_ps[i + 1][1]) ** 2)
  
  print(sum_dist / math.factorial(N))

Submission status: Accepted

Solution code:
a = int(input())
ar = []
br = []
for i in range(a):
    x,y = map(int,input().split(" "))
    ar.append([x,y])
    br.append([x,y])
count = 0
for i in range(a):
    for j in range(a):
        if i != j:
            count += ( (abs(ar[i][0] - br[j][0]) ** 2 + (abs(ar[i][1] - br[j][1])) ** 2) )** 0.5
print(count / a)

Submission status: Accepted

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

from itertools import permutations

a = (permutations(p))

from math import sqrt

def dis(a):
    sum = 0
    for i in range(n-1):
        sum += sqrt( (a[i][0]-a[i+1][0]) ** 2 + (a[i][1]-a[i+1][1]) ** 2 )
    return sum

b = map(dis, a)

from statistics import mean

print(mean(b))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from math import sqrt
input = sys.stdin.readline
N = int(input())
p = []
for _ in range(N):
  p.append(list(map(int, input().split())))
def dist(x1, y1, x2, y2):
  return sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
res = 0
vis = set()
c = 0
def fact(n):
  r = 1
  for i in range(1, n + 1):
    r *= i
  return r
def dfs(n):
  global vis
  global res
  global c
  for x in range(N):
    if x in vis: continue
    vis.add(x)
    res += dist(p[n][0], p[n][1], p[x][0], p[x][1]) * fact(N - len(vis))
    dfs(x)
    vis.discard(x)
  if len(vis) == N: c += 1

for y in range(N):
  vis.add(y)
  dfs(y)
  vis.discard(y)


print(res / c)

Submission status: Accepted

Solution code:
n = int(input().strip())
town = [list(map(int, input().split())) for _ in range(n)]
def dist(p, q):
  return ((p[0]-q[0]) ** 2 + (p[1]-q[1]) ** 2) ** 0.5
s = sum(dist(p, q) for p in town for q in town)
avg = s / n
print ("{:.10f}".format(avg))

Submission status: Accepted

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

n=int(input())
p=[list(map(int,input().split())) for i in range(n)]
ans=0
for i in range(n):
  for j in range(i+1,n):
    ans+=dis(p[i],p[j])
print(ans*2/n)

Submission status: Accepted

Solution code:
import itertools as iter
n = int(input())
li = [list(map(int,input().split())) for i in range(n)]
com = list(iter.permutations(li))
start = com[0]
ans = 0
for i in com:
    for j in range(n-1):
        a,b=i[j]
        c,d=i[j+1]
        ans+=((c-a)**2+(d-b)**2)**0.5
print(ans/len(com))

Submission status: Accepted

Solution code:
import numpy as np

def main():
    N = int(input())
    x = []
    for i in range(N):
        x.append(list(map(int, input().split())))
    X = np.array(x)
    j = 0
    for i in range(N-1):
        for k in range(i+1, N):
            j += np.linalg.norm(X[i] - X[k], ord=2)

    print(2*j/N) # 2(N-1)!/N!

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools
import math

n = int(input())
l =[]
for i in range(n):
    x,y = map(int,input().split())
    l.append((x,y))
d = [[0]*n for i in range(n)]
for i in range(n-1):
    for j in range(n):
        xy = math.sqrt((l[i][0]-l[j][0])**2 + (l[i][1]-l[j][1])**2)
        d[i][j] = xy
        d[j][i] = xy
t = (i for i in range(n))
p = list(itertools.permutations(t))
sum = 0
nn = math.factorial(n)
for i in p:
    for j in range(n-1):
        sum += d[i[j]][i[j+1]]
ans = sum / nn
print(ans)

Submission status: Accepted

Solution code:
import math
n=int(input())
A=[]
sum=0
for i in range(n):
  a,s=(int(x) for x in input().split()) 
  A.append((a,s))
for i in A:
  for i2 in A:
    sum+=math.sqrt((i[0]-i2[0])**2+(i[1]-i2[1])**2)
print(sum/n)

Submission status: Accepted

Solution code:
import math
 
def factorial(n):
    if n == 0:
        return 1.0
    else:
        return n*factorial(n-1)
 
 
n = int(raw_input())
k = n
arr = []
while(k > 0):
    x, y = map(int, raw_input().split())
    arr.append((x, y))
    k -= 1
 
total = 0.0
for i in range(n):
    x1 = arr[i][0]
    x2 = arr[i][1]
    for j in range(i+1, n, 1):
        y1 = arr[j][0]
        y2 = arr[j][1]
        dist = (x1-y1)*(x1-y1) + (x2-y2)*(x2-y2)
        dist = float(math.sqrt(dist))
        dist = dist * float((factorial(n-1)*2))
        total += dist * float(1/factorial(n))
 
print total

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    C=[0]*n
    for i in range(n):
        x,y=map(int,input().split())
        C[i]=complex(x,y)

    from itertools import product
    S=sum(abs(C[i]-C[j]) for i,j in product(range(n),repeat=2))
    print(S/n)
resolve()

Submission status: Accepted

Solution code:
import math

def distance(point1, point2):
  return math.sqrt((point1[0]-point2[0])**2 + (point1[1]-point2[1])**2)

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

sum = 0
fact = math.factorial(N-1)
for i in range(0, N):
  for j in range(0, N):
    if i == j:
      continue
    else:
      sum += distance(x_y_list[i], x_y_list[j]) * fact

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

Submission status: Accepted

Solution code:
import math

lst = []
n = int(input())
dis_sum = 0
for i in range(n):
  a,b = map(int,input().split())
  lst.append([a,b])
for i in lst:
  for j in lst:
    x = abs(j[0]-i[0])
    y = abs(j[1]-i[1])
    dis_sum += math.sqrt(x**2 + y**2) 
print(dis_sum / n)

Submission status: Accepted

Solution code:
N = int(input())
L=[[int(j) for j in input().split()] for i in range(N)]
from math import factorial, sqrt
from itertools import permutations
S = 0
def k(a, b):
    return sqrt((a[0] - b[0])**2 + (a[1] - b[1])**2)
for l in permutations(L):
    S += sum([k(l[i], l[i+1]) for i in range(N-1)])

print(S/factorial(N))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

from itertools import permutations

def main():
    n = int(input())
    town = [tuple(map(int,input().split())) for i in range(n)]
    p = [i for i in range(n)]

    distsum = 0
    count = 0
    for p2 in permutations(p):
        for i in range(1,n):
            d1 = town[p2[i]]
            d2 = town[p2[i-1]]
            distsum += ((d1[0]-d2[0]) ** 2 + (d1[1]-d2[1]) ** 2) ** 0.5
        count += 1

    print(distsum / count)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
L=[[int(j) for j in input().split()] for i in range(N)]
from math import factorial, sqrt
S = 0

def solve(L, r):
    global S
    if len(L) == 0:
        for i in range(N-1):
            x, y = r[i]
            x2, y2 = r[i+1]
            S += sqrt((x - x2)**2 + (y - y2)**2)
    for i, v in enumerate(L):
        if len(L) == N:
            solve(L[:i] + L[i+1:], [v])
        else:
            solve(L[:i] + L[i+1:], r + [v])

solve(L, [])
print(S/factorial(N))

Submission status: Accepted

Solution code:
import math
from sys import exit, stdin
N = int(stdin.readline().rstrip())
xy = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N)]

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

Submission status: Accepted

Solution code:
import math as ma

n = int(input())
m = [list(map(int, input().split())) for i in range(n)]
t = [[0 for j in range(n) ] for i in range(n)]
ans = 0

for i in range(n):
    for j in range(n):
        if i == j or t[i][j] > 0:
            pass
        else:
            x = m[i][0] - m[j][0]
            y = m[i][1] - m[j][1]
            l = x**2 + y**2
            t[i][j] = ma.sqrt(l)
            t[j][i] = ma.sqrt(l)
    ans += sum(t[i])    

print(ans/n)

Submission status: Accepted

Solution code:
n=int(input())
c=1
for i in range(1,n+1):
    c *=i
a=[]
b=[]
for i in range(n):
    x,y=map(int,input().split())
    a.append(x)
    b.append(y)
d=[]
for i in range(n):
    for j in range(i+1,n):
        k=((a[i]-a[j])**2+(b[i]-b[j])**2)**0.5
        d.append(k)

total=c/n*2*sum(d)
print(total/c)

Submission status: Accepted

Solution code:
import math
import itertools

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

for pattern in list(itertools.permutations(range(n))):
    dist = 0
    for i in range(len(pattern)-1):
        dist += math.sqrt((town_list[pattern[i]][0]-town_list[pattern[i+1]][0])**2 + (town_list[pattern[i]][1]-town_list[pattern[i+1]][1])**2)
    ave_list.append(dist)

print(sum(ave_list)/len(ave_list))

Submission status: Accepted

Solution code:
import numpy as np
import itertools

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

grid = np.zeros((n, n))
for i in range(n):
    for j in range(n):
        grid[i][j] = ((x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2) ** 0.5

sum = 0
cnt = 0

for i in itertools.permutations(np.arange(n)):
    cnt += 1
    dist = 0
    for j in range(n - 1):
        dist += grid[i[j]][i[j + 1]]
    sum += dist
print(sum / cnt)

Submission status: Accepted

Solution code:
import math
N = int(input())
#距離の箱を作成
kyori = []
kyori2 = []
kyori3 = []
sumation = 0
for i in range(N):
    #N回繰り返す
    kyori.append(list(map(int,input().split())))
#x間の距離、y間の距離を算出
#ここで、2→1と1→2などは同じ距離なので計算しない
x_distance = 0
y_distance = 0
for i in range(0,N):
    for j in range(i+1,N):
        x_distance = (kyori[i][0]-kyori[j][0])**2
        y_distance = (kyori[i][1]-kyori[j][1])**2
        #xとyの距離を計算(sqrt導出)
        Kyorixy = math.sqrt(x_distance + y_distance)
        kyori2.append(Kyorixy)
if len(kyori2) == 1:
    print(kyori2[0])
else:
  goukei = sum(kyori2)*2/N
  print(goukei)

Submission status: Accepted

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

sum = 0
for i in range(n):
  for j in range(i, n):
    x = abs(position[i][0] - position[j][0])
    y = abs(position[i][1] - position[j][1])
    sum += math.sqrt(x*x + y*y)

print(sum*2/n)

Submission status: Accepted

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

sum = 0
for i in range(n):
    for j in range(n):
        if i != j:
            sum += pow(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2), 0.5)

sum = sum / n
print(sum)

Submission status: Accepted

Solution code:
import itertools
import math

N = int(input())
Fac = math.factorial(N)
x = []
y = []
X = []
Y = []
leng = []
tmp = 0
for i in range(N):
    tmp = list(map(int,input().split()))
    x.append(tmp[0])
    y.append(tmp[1])
for i in itertools.permutations(x):
    X.append(i)
for i in itertools.permutations(y):
    Y.append(i)
for i in range(Fac):
    try:
        leng.append(((((X[i][0]-X[i][1]) ** 2) + ((Y[i][0]-Y[i][1]) ** 2)) ** 0.5))
    except:
        pass
tmp = 0
for i in range(Fac):
    tmp += leng[i]
tmp *= (N-1)
ans = tmp / Fac
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
import math

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

dists_sum = 0
for order in permutations(range(N)):
    for i in range(1, N):
        cp, cn = order[i - 1], order[i]
        dists_sum += math.hypot(X[cn] - X[cp], Y[cn] - Y[cp])
print(dists_sum / math.factorial(N))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int, x: "List[int]", y: "List[int]"):
    from math import sqrt
    def distance(x1: float, y1: float, x2: float, y2: float):
        return sqrt((x2-x1)**2 + (y2-y1)**2)

    ans = []
    import itertools
    for i in itertools.permutations(list(range(N)), N):
        t = 0
        for j in range(1,N):
            t += distance(x[i[j-1]], y[i[j-1]], x[i[j]], y[i[j]])
        ans.append(t)

    print(sum(ans)/len(ans))
    
    return



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

n = int(input())
path = list(itertools.permutations(set(range(n))))

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


def dist(x, y):
    return (x ** 2 + y ** 2) ** 0.5


check = list()
for p in path:
    for i in range(len(p) - 1):
        total += dist(town[p[i]][0] - town[p[i + 1]][0], town[p[i]][1] - town[p[i + 1]][1])

print(total / len(path))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

import itertools, math

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

tmp = [i for i in range(n)]
pairs = list(itertools.combinations(tmp, 2))
ds = {}
for a, b in pairs:
  d = math.sqrt((lst[a][0] - lst[b][0]) ** 2 + (lst[a][1] - lst[b][1]) ** 2)
  if not a in ds:
    ds[a] = {}
    ds[a][b] = d
  else:
    ds[a][b] = d

cands = list(itertools.permutations(tmp, n))
result = 0
for cand in cands:
  res = 0
  for i, elem in enumerate(cand[:-1]):
    if elem in ds and cand[i+1] in ds[elem]:
      res += ds[elem][cand[i+1]]
    else:
      res += ds[cand[i+1]][elem]
  result += res
print(result / len(cands))

Submission status: Accepted

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

Submission status: Accepted

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

s=0.0
for i in range(n-1):
  for j in range(i+1,n):
    s += ((v[i][0]-v[j][0])**2+(v[i][1]-v[j][1])**2)**(1/2)
print(2/n*s)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# C
def perm(N):
    ans = 1
    for i in range(2, N+1):
        ans *= i
    return ans

N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
distance_list = []
for i in range(N-1):
    for k in range(i+1, N):
        distance_list.append(((xy[i][0] - xy[k][0]) ** 2 + (xy[i][1] - xy[k][1]) ** 2) ** 0.5)
##print(distance_list)
tmp = sum(distance_list)
cnt = perm(N-1) * 2
##print(tmp, cnt, perm(N))
print(tmp * cnt / perm(N))