Даю 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
На плоскости заданы 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
Answers & Comments
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])