Найти минимальное множество прямых

[Inokentiy]

На плоскости заданы N точек. Найти минимальное множество прямых, на которых можно разместить все точки.
Не понятно каким образом найти имено минимальное множество прямых???

[eoln]

Можно в лоб.
Строим всевозможные прямые, их кол-во <= сумма от 1 до N-1.
Для каждой прямой заводим массив где будут хранится порядковые номера точек, которые принадлежат этой прямой и их кол-во.
Проверять принадлежность так: дана прямая на точках O(x0, y0), Oi(xi, yi), её характеристики Следующие:
A:=yi-y0;
B:=x0-xi;
C:=-A*x0-B*y0; (пишу на память, могу ошибиться в знаках)
точка Z(x, y) принадлежит прямой, если равенство C=-A*x-B*y верно. .

Ответ получаем в цикле. Берём прямые которые содержат N точек, затем N-1, N-2 точек, и т.д. пока точки не кончатся. При этом каждый раз при выборе прямой нужно будет вычёркивать из расчёта эти точки (т.е. понижать число точек у тех прямых, которые содержат точки выбранной прямой). При каждой удачной выборке увеличиваем счётчик. В конце может остаться одна точка, тогда просто увеличим счётчик ещё раз. Этот счётчик и будет ответом.

Описание длинное и страшное, но код должен быть небольшой. При построении прямых можно использовать рекурсию.
P.S. Это всего-лишь алгоритм, оптимизации никакой.

[Inokentiy]

Сообщение от eoln

Этот счётчик и будет ответом.

Ответом должен быть не счетчик а множество прямых,но с этим еще ладно.
А что если у нас есть три точки,не лежащие на одной прямой?
Тогда мы берем прямую с N-1 то есть с двумя точками, допустим сохраняем ее в какой-нибудь структуре данных(например в либо массиве,ли на крайний случай в линейном списке) и удаляем первые две точки,а что делать с третьей точкой и как проводить через нее прямую, если точек больше нет???

[Serebro]

Если после исключений останется одна точка, то пишем в результат +1 прямую (прямая с любой точкой).

[LeBron]

Все правильно, если влоб - то именно так и делать, без любых оптимизаций будет О(N^3) (N^2 прямых, порядка N вхождений в перебор).

[Inokentiy]

Сообщение от eoln

в лоб

А что тогда значит не в лоб?
И можно ли здесь применить динамическое программирование и рекурсию?(как?)

[Inokentiy]

Сообщение от eoln

При построении прямых можно использовать рекурсию.

Как именно ее использовать?

[LeBron]

Я даже неверно оценил, там не куб, а биквадрат, так как на каждом шагу надо будет еще проверять все точки на принадлежность прямой. Можно оптимизировать до куба на логарифм, если вкрутить сортировку и бинарник по парамерту.

[eoln]

Ага, в проекте пример решения в лоб без оптимизации с графикой и объяснением. Без графики для 100 точек - 0,3 сек, для 200 точек - 3 сек, для 400 точек 10 сек и 130 МБ памяти, для 1000 точек у меня оперативки не хватило

[LeBron]

решение за куб: сначала сгенерить все прямые и посчитать для каждой, сколько на ней точек, потом жадником - выбрасываем лучшую прямую, пересчитываем значения для всех остальных (суммарная асимптотика куб, так как в общей сложности выбросим все точки и для каждой при выбрасывании проверим квадрат прямых),снова ищем максимум (за квадрат, просмотром всех прямых), и так далее. В общей сложности чистый куб, в худшем случае для 400 точек в секунду уложится. На рэндом-тестах должен быть еще быстрее Надо будет подумать над квадратом, у меня есть догадка, как его сделать, достаточно прикрутить метки принадлежности, сейчас додумаю и после обеда напишу, если действительно подходит.
Быстрее квадрата наверно нельзя, так как все равно надо все прямые просмотреть.