input list X's shape :【N,2】;
return:max pairwise distance using the bubblesort function
问题中没有提供冒泡函数,所以得先写一个冒泡排序函数。如果题主有,请自行替换。
>>> def bubblesort(arr):
result = arr[:]
for i in range(len(arr)-1):
for j in range(len(arr)-1-i):
if result[j] > result[j+1]:
result[j], result[j+1] = result[j+1], result[j]
return result
>>> bubblesort([3,8,2,6,7,1,4]) # 测试冒泡排序
[1, 2, 3, 4, 6, 7, 8]
>>> def max_paipwise_distance(x):
dist = list()
for i in range(len(x)-1):
for j in range(i+1, len(x)):
dist.append(pow((pow(x[i][0]-x[j][0], 2) + pow(x[i][1]-x[j][1], 2)), 0.5))
return bubblesort(dist)[-1]
>>> max_paipwise_distance([[3,4], [0,0], [-3,-4]]) # 测试
10.0
def bubblesort(s):
# we need this because we're gonna divide by zero
old_settings = np.seterr(all="ignore")
N = N_segments # just shorter, could also use len(s)
# we repeat p0 and p1 along all columns
p0 = np.repeat(s[:,0:3].reshape((N, 1, 3)), N, axis=1)
p1 = np.repeat(s[:,3:6].reshape((N, 1, 3)), N, axis=1)
# and q0, q1 along all rows
q0 = np.repeat(s[:,0:3].reshape((1, N, 3)), N, axis=0)
q1 = np.repeat(s[:,3:6].reshape((1, N, 3)), N, axis=0)
# element-wise dot product over the last dimension,
# while keeping the number of dimensions at 3
# (so we can use them together with the p* and q*)
a = np.sum((p1 - p0) * (p1 - p0), axis=-1).reshape((N, N, 1))
b = np.sum((p1 - p0) * (q1 - q0), axis=-1).reshape((N, N, 1))
c = np.sum((q1 - q0) * (q1 - q0), axis=-1).reshape((N, N, 1))
d = np.sum((p1 - p0) * (p0 - q0), axis=-1).reshape((N, N, 1))
e = np.sum((q1 - q0) * (p0 - q0), axis=-1).reshape((N, N, 1))
# same as above
s = (b*e-c*d)/(a*c-b*b)
t = (a*e-b*d)/(a*c-b*b)
# almost same as above
pairwise = np.sqrt(np.sum( (p0 + (p1 - p0) * s - ( q0 + (q1 - q0) * t))**2, axis=-1))
# turn the error reporting back on
np.seterr(**old_settings)
# set everything at or below the diagonal to 0
pairwise[np.tril_indices(N)] = 0.0
return pairwise
def bubbleSort(arr):
n = len(arr)
for i in range(n-1):
for j in range(n-1-i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
lis = list(input())
print(bubbleSort(lis))