Question

Даю 20 баллов!!!
На плоскости заданы N (1 <= N <= 770) точек с номерами от 1 до N,
в точках с координатами (x,y) - x и y в диапазоне 0..15,000.
Спрашивается сколько групп из трех точек на одной прямой
существует на данном поле. Известно, что никакие две точки не имеют
одинаковые координаты. Выведите все такие тройки в порядке
возрастания номеров точек.
Формат вывода

Первая строка содержит одно целое число K - количество всех троек точек,
расположенных на одной прямой. Если у нас есть ровно 4 точки, расположенных
на одной прямой, то это дает четыре множества по три точки на одной прямой.
Каждая последуюшие K строк содержит три разделенных одиночными пробелами
целых числа - номера точек, расположенных на одной прямой. Строки
отсортированы в порядке описанном выше. Вывод должен быть пустым, если нет
точек расположенных на одной прямой.

Пример ввода

8
0 0
0 4
1 2
2 4
4 3
4 5
5 1
6 5
Пример вывода

1
1 3 4

Answer 1

from collections import defaultdict

def find_triples(points):

n = len(points)

# dictionary to store the point numbers

groups = defaultdict(list)

for i in range(n):

for j in range(i + 1, n):

for k in range(j + 1, n):

if (points[j][1] - points[i][1]) * (points[k][0] - points[j][0]) == (points[k][1] - points[j][1]) * (points[j][0] - points[i][0]):

# points are on the same line

groups[(points[i], points[j], points[k])].append(i + 1)

groups[(points[i], points[j], points[k])].append(j + 1)

groups[(points[i], points[j], points[k])].append(k + 1)

# sort the point numbers

for group in groups:

groups[group] = sorted(groups[group])

return groups

points = [(0, 0), (0, 4), (12, 24), (4, 3), (4, 5), (5, 1), (6, 5)]

result = find_triples(points)

print(len(result))

for group in result:

print(result[group])