Почему GCD необходим в этом алгоритме, обнаружив, что все группы по трем точкам являются коллинеарными в картезианской к ⇐ Python

[Anonymous]

Я пытался решить эту задачу кодирования: «Учитывая массив пар, каждая пара (x, y), которые оба являются целочисленными, обозначает координату точки в картезианской координатной плоскости, найдите много групп из трех точек коллинеар . "< /p>
Оказывается, это ниже правильный алгоритм: < /p>

Код: Выделить всё

def gcd(x, y):
if y == 0:
return x
else:
return gcd(y, x % y)

def how_many_3point_in_line( points ):
ans = 0
n = len( points )
for i in range( n - 2 ):
slopes = defaultdict( int )
for j in range( i + 1, n ):
dy, dx = points[i][1] - points[j][1], points[i][0] - points[j][0]
gcd_num = gcd( dx, dy )
slopes[( dy // gcd_num, dx // gcd_num )] += 1
for _, occ in slopes.items():
ans += math.comb( occ, 2 )
return ans

Очевидно, что GCD используется для представления наклона, какой вопрос он решает?

Подробнее здесь: https://stackoverflow.com/questions/794 ... -are-colli