Задача про точки на плоскости

[Единорог]

Добрый вечер! Задано множество точек на плоскости. Необходимо найти две такие точки, что разница между количеством оставшихся точек, лежащих по разные стороны от прямой, соединяющей две искомые точки, была минимальной.

[Единорог]

Уважаемый модератор. Извините, я не студент и не учащийся. Тему переименовал. Алгоритм нужен для решения другой, более крупной задачи

Странно. "Более крупная задача" не потребует знания элементарных вещей?
В любом случае в раздел для студентов...
Модератор.

[Voody]

Перебираем все пары точек.
Для каждой пары (х1,у1) (х2,у2) считаем:
1) уравнение прямой, проходящей через эти точки.
По формуле: (х-х1)*(у2-у1)=(х2-х1)*(у-у1). Получаем уравнение типа a*x+b*y+c=0
2) для каждой другой точки плоскости считаем, по какую сторону от прямой она лежит. Её координаты подставляются в уравнение прямой и смотрится результат. Если <0 , то по одну сторону; если >0 , то по другую сторону.
3) вычисляем разницу между количеством точек и сравниваем с минимальной.
В конце получается пара искомых точек

[LeBron]

Как-то пропустил тему раньше, вот сегодня заметил, что за задачу тут подняли. Довольно интересная. Бредобрутфорсное решение хоть и рабочее, но для серьезных задач не подходит. Если правильно понял задание, то задача полностью описывается через тета-множества. Следовательно, ее решение должно работать за O(n^2) или еще быстрее. Сяду думать, как решать, а то "общее" решение за квадрат или за n*log(n) не подходит для некоторых "коварных" случаев.
З.Ы. Уже придумал, как делать за О(n*n*log(n)) для общего случая и за O(n*log(n)) для точек, среди которых никакие 3 не лежат на одной прямой. Просветите, как зе квадрат сделать, а то не получается.