import random def rotate(a,b,c): return (b[0]-a[0])*(c[1]-b[1])-(b[1]-a[1])*(c[0]-b[0]) def qsort(start,a,P): # 2. Упорядкування даних точок if (len(P)==1) or (len(P)==0): # якщо масив порожній або одноелементний, return P # тобто немає що упорядковувати, … k = random.randint(0,len(P)-1) # випадковим чином вибрати значення елемента # масиву, щоб уникнути переповнення стеку # при упорядкованих даних dk=abs(a[start][0]-a[P[k]][0])+abs(a[start][1]-a[P[k]][1]) left = [] center = [] right = [] for j in range(len(P)): dj=abs(a[start][0]-a[P[j]][0])+abs(a[start][1]-a[P[j]][1]) x = rotate (a[start],a[P[k]],a[P[j]]) if x<0: left.append(P[j]) elif x>0: right.append(P[j]) else: if dj>dk: left.append(P[j]) elif dj