Минимальное множество прямых (рекурсия с возвратом) Опции

[Даша]

Всем доброго времени суток! Прошу помочь со следующей задачей: найти минимальное множество прямых, проходящих через все заданные точки. То есть заданы координаты точек и ответом должно быть число прямых. Не знаю как организовать перебор всех вариантов, очень прошу написать хотя бы в общем виде сам алгоритм.

[Lapp]

Всем доброго времени суток! Прошу помочь со следующей задачей: найти минимальное множество прямых, проходящих через все заданные точки. То есть заданы координаты точек и ответом должно быть число прямых. Не знаю как организовать перебор всех вариантов, очень прошу написать хотя бы в общем виде сам алгоритм.

И это нужно сделать с помощью рекурсии? В целом, ничего сложного, но есть непонятные моменты..

Допустим, точки заданы массивом (то есть, упорядочены). Делаешь процедуру, которая делает две вещи (либо/либо, как обычно в рекурсии):
1. Если точек 2 или больше, то берет следующую точку и проводит все прямые через нее и все остальные и добавляет их к списку, если их там еще нет; после этого "выкидывает" эту тучку из массива и вызывает себя же.
2. Если точка только одна - выходит.

Таким образом будут проведены все прямые. Смысл твоей задачи состоит в том, чтоб отсеять повторы, поэтому нужно всякий раз проверять, не включена ли прямая уже в список. А для этого нужно уметь уметь сравнивать прямые. Например, если две прямые заданы в виде y=ax+b, то они одинаковые, если a₁ и b₂ соответственно равны a₂ и b₂. Тут возникает оджин вопрос: как заданы координаты точек? Это действительные числа или целые? Действительные сравнивать несколько труднее..

Говори, что непонятно.