Задача на графы, Очень срочно! Опции

[klik1602]

Помогите пожалуйста!! Завтра сдавать, я в графах ни бум-бум...очень прошу!
23. На плоскости заданы 2n точек своими координатами. Найдите уравнение какой-либо прямой, делящей данное множество точек на два подмножества по n точек.

[TarasBer]

1. Нам надо найти прямую, которая не параллельная ни одной a[i]a[j].
2. Пусть её уравнение M*x+N*y+k=0. Сортируем массив чисел M*a[i].x + N*a[i].y + k (то есть для каждой точки берём такое число, потом сортируем массив таких чисел). Получили массив b[i]. Берём c := (b[n]+b[n+1])/2 - ну то есть число из середины массива. В качестве ответа берём M*x+N*y+(k-c): ведь у ровно половины точек число M*a[i].x + N*a[i].y + k-c будет строго положительно, а у другой половины - строго отрицательно.

Вот по поводу пункта 1 что я думаю.
Метод взятия случайной прямой вида

a:=random*2*pi;
cos(a)*x + sin(a)*y = 0;

с высокой вероятностью быстро найдёт ответ, если он есть. А его может не быть.
Если есть совпадающие точки, то мы уже обламываемся, всё резко усложняется. Детерминированный алгоритм придумать для такого случая я вообще не могу.

Если все разные. Можно тупо перебрать, да (только не по тройкам точек, а по парам). Мне это не нравится.

Можно взять минимальное ненулевое dx := a[i].x-a[j].x (для этого надо отсортировать координаты x и перебрать пары соседних). Взять максимальное dy := a[i].y-a[j].y (для этого надо вычесть максимум из минимума)

Взять x*2*dy - y*dx = 0 в качестве искомой прямой: ведь вектор (dx; 2*dy) не параллелен ни одному отрезку a[i],a[j], потому что его тангенс наклона вдвое превышает все возможные тангенсы наклона отрезков, соединяющих точки из набора.

правка: увеличил буквы в уравнении прямой, а то тавтология

Сообщение отредактировано: TarasBer - 4.03.2011 9:58