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

[klik1602]

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

[Krjuger]

Условие не совсем понятно.А что если некоторые точки будут лежать на искомой прямой,то к какому подмножеству они буду относиться?Как можно задачать координаты точек?(целые или вещественные числа?)И самое главное,как множество точек,которые как таковой между собой никак не связаны, относится к графам?Если есть какие то конретные предписания,как это делать,то желательно о них упомянуть.И в каком виде нужно найти уравнение прямой?Можно например, как функцию у от х ,можно как точку и угол наклона.....

[klik1602]

у меня только это условие и никаких пояснений( задача относиться к теме комбинаторные алгоритмы и алгоритмы на графах, которую я совсем не пониманию..

Сообщение отредактировано: klik1602 - 4.03.2011 4:29

[Lapp]

23. На плоскости заданы 2n точек своими координатами. Найдите уравнение какой-либо прямой, делящей данное множество точек на два подмножества по n точек.

Допустим, координаты точек содержатся в массиве/массивах.
1. Упорядочиваем этот/эти массив/массивы по возрастанию X.
2. Если x_n <> x_n+1, то искомое равнение есть x = (x_n + x_n+1) / 2;
3. Если x_n = x_n+1, то..
4. найти минимальный ненулевой угол, опирающийся на точки из данного множества (назовем его A);
5. произвести поворот системы координат на A/2 (вокруг произвольной точки).
6. Перейти к 1.

Решение, правда, не имеет особого отношения к графам.. И еще: пункты 4 и 5, возможно, можно заменить на что-то попроще, немного менее детерминированное - например, поворот на случайный угол до тех пор, пока не выполнится условие в п.2.

[klik1602]

ммм, попробую завтра утром сделать, если успею, ночью голова не варит совсем, спасибо большое вам..
не понимаю как вот это реализовать
4. найти минимальный ненулевой угол, опирающийся на точки из данного множества (назовем его A);
5. произвести поворот системы координат на A/2 (вокруг произвольной точки).

Сообщение отредактировано: klik1602 - 4.03.2011 5:16

[Lapp]

не понимаю как вот это реализовать

Реализовать это можно полным перебором по всем точкам, примерно так:

aMin:= Pi;
for i:=1 to 2*n do
  for j:=1 to 2*n do 
    if i<>j then
      for k:=i+1 to 2*n do begin
        a:= Angle(j,i,k);
        if (a>Eps) and (a<aMin) then aMin:=a
      end;

Тут Angle(x,y,z) - это величина угла между лучами, проведенными из точки с номером y в точки с номерами x и z (надо написать такую функцию); Eps - просто очень малое число (скажем, 1E-7).

Но для начала лучше вращать на случайный угол (см. конец моего первого мессаджа). Угол генерировать так:

a:= Random*Pi;

Да, и еще: если был поворот, то нужно потом применить обратое преобразование (обратный поворот) к найденной прямой. Если делался (многогратный) поворот на случайный угол, то их нужно суммировать (центром поворота лучше всего выбрать начало координат).

Получается несколько громоздко, если честно.. Можно попробовать придумать что-то более элегантное )). Но геометрия будет все равно та же, я думаю.

[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 13:58

[klik1602]

добрый вечер, снова возвращаюсь к этой программе, которую я так и не сдала. Большое спасибо, за предложенные алгоритмы Lapp и TarasBer, хотела бы разобраться в вашем варианте TarasBer. Я так понимаю последовательность действий такая:
1. записываем координаты точек в массивы X и Y
2. далее нужно найти прямую,

которая не параллельная ни одной a[i]a[j]

, вот что такое a[i]a[j] не совсем понятно,
далее

Пусть её уравнение M*x+N*y+k=0.

, я так понимаю, М=cos(a), N=sin(a), где a:=random*2*pi;
подставим всё это мы получаем значения k, которые записываем в массив b[i] ????? или я не так понимаю, помогите разобраться пожалуйста..
3.

Берём c := (b[n]+b[n+1])/2

4.

В качестве ответа берём M*x+N*y+(k-c)

не откажите в помощи..

[Krjuger]

a[i]a[j]-это 2 точки нашего исходного массива,принципи это то, что нужно чтобы задать любую прямую на плоскости(пространстве))Но так же учтите,что решение TarasBer не универсально.

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

Сообщение отредактировано: Krjuger - 27.03.2011 6:05

[Lapp]

Я думаю, что в условии должно быть требование, что никакие две точки не слвпадают, иначе задача просто нерешаема.

a[i] и a[j] - две точки.
a[i]a[j] - прямая, проходящая через a[i] и a[j]

[klik1602]

Цитата
Пусть её уравнение M*x+N*y+k=0.
, я так понимаю, М=cos(a), N=sin(a), где a:=random*2*pi;
подставим всё это мы получаем значения k, которые записываем в массив b[i] - так значит вот этот пункт верный?

[Krjuger]

я так понимаю, М=cos(a), N=sin(a), где a:=random*2*pi;

Не совсем,смотрите его тождества.

cos(a)*x + sin(a)*y = 0;
M*x+N*y+k=0

Если к равно 0,то да будет так,как вы написали,а так все не так просто получается.

Я думаю, что в условии должно быть требование, что никакие две точки не слвпадают, иначе задача просто нерешаема.

Почему не решаема??Мне кажется она усхожнится,возможно в разы,но будет решаема,первое,что я вижу,это появится зависимость от того сколько точек в 1 позиции,ну и соотвественно усложнятся некоторые моменты,такие как c := (b[n]+b[n+1])/2 уже некоректно.

А вообще у данного решения есть 1 маленький нюанс,что если уравнение прямой магическим образом по стечению обстоятельств будет проходить через нашу точку a[i],к какому множеству ее тогда причислять?

Скорее всего,когда студенту дается так мало условий,он имеет право,сам сузить задачу,приведя соответствующие аргументы,почему он не рассматривает этот случай и эту возможность.

Сообщение отредактировано: Krjuger - 27.03.2011 17:36

[klik1602]

нашла на просторах интернета похожую задачу на мою среди олимпиадных задач, к ней был приложен алгоритм решения, довольно подробно расписанный что и к чему, сейчас его пробую реализовать и вроде получается, не знаю, разрешено ли в форуме давать ссылки на другие сайты(( если можно, то я скину ссылочку, кому интересно..

[Krjuger]

Вы можете взять и скопировать этот алгоритм суда,если хотите,и да,здесь можно давать ссылки на сторонние ресурсы,по крайней мере,админы переодически помогают,давая ссылки на нужную информацию с сторонних ресурсов.

Сообщение отредактировано: Krjuger - 27.03.2011 21:18

[klik1602]

Отсортировав координаты точек в порядке неубывания Х-овых координат, а в случае одинаковых Х-овых координат в порядке неубывания У-овых координат, находим координаты средней точки (находящуюся в позиции n div 2+1), пусть это точка (Х0,У0). При этом множество точек оказалось разбито на 3 части: точки, лежащие на прямой х=Х0; точки, лежащие левее прямой х=Х0; точки, лежащие правее прямой х=Х0. Представим, что точки, лежащие левее прямой х=Х0 ( точки, лежащие правее прямой х=Х0) лежат в пределах некоторого прямоугольника, где Х1 (Х2) координаты его правого (левого) края. Тогда легко понять, что существует прямая с достаточно большим углом наклона, которая разделяет эти части. Осталось разделить только точки на прямой, чтобы количество точек в получившихся частях было соответствующим (т.е. пересечение прямой с прямой х=Х0). Если количество точек нечетно, то искомая линия проходит через среднюю точку, иначе над средней точкой (но под предыдущей, если она лежит па прямой х=Х0).

Определим:

Х1 - может быть легко найдена просмотром массива Х-овых координат справа налево от средней точки до нахождения первой координаты, отличной от Х0. Если такая координата не найдена, то Х1=Х0-1.

Х2 - может быть легко найдена просмотром массива Х-овых координат слева направо от средней точки до нахождения первой координаты, отличной от Х0. Если такая координата не найдена, то Х1=Х0+1.

У1 - это У-овая координата точки, предшествующей средней точке, если Х-ая ее координата равна Х0, или равна У0-1, если Х-овая координата точки, предшествующей средней точке, не равна Х0.

После того, как Х0,У0,Х1,У1 найдены, осталось написать уравнение прямой через точки с координатами (Х2,У2) (Х3,У3), определяемыми по следующему правилу:

если N - четно

то Х2=Х0; У2=(У0+У1)/2, Х3=Х0+Z/2,У3=У0-Ymax+Ymin

иначе Х2=Х0; У2=У0, Х3=Х0+Z/2,У3=У0-Ymax+Ymin

где Ymax- максимальная У-овая координата, Ymin - минимальная У-овая координата, Z=min(Х0-Х1,Х2-Х0).

кстати я всё сделала по этому алгоритму, всё работает) но уверенности в том что правильно нету, не согласитесь его посмотреть))?

Сообщение отредактировано: klik1602 - 27.03.2011 23:29

[Lapp]

но уверенности в том что правильно нету, не согласитесь его посмотреть))?

И хорошо, что нет уверенности. Алгоритм неверный. Но рациональное зерно в нем есть, и он может быть довольно просто исправлен.

[klik1602]

он может быть довольно просто исправлен.

подскажите хотя бы в каком месте ошибка, чтобы исправить.

[Krjuger]

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

Чем отличается алгоритм от нужной вам задачи.

При этом множество точек оказалось разбито на 3 части: точки, лежащие на прямой х=Х0; точки, лежащие левее прямой х=Х0; точки, лежащие правее прямой х=Х0

Для вашей задачи недопустимо,чтобы точки лежали на прямой,иначе как определять к какому множеству они будут относиться.

Если количество точек нечетно, то искомая линия проходит через среднюю точку.

Этот вариант тоже рассматривать не нужно,потому что у вас всегда четное количество точек.

иначе над средней точкой (но под предыдущей, если она лежит па прямой х=Х0).

Возможно я что то напутал или неверно понял,но это утверждение не верно(точнее оно не полное).Если надо могу привести пример.

[klik1602]

вот код:

program L15_23;
const
 maxn=100;
type
 koardinat=array[1..maxn] of real;
var
 x,y:koardinat;
 k,n:integer;
 x0,y0,x1,x2,y1,miny,maxy:real;

procedure VvodKoardinat (n:integer; var x,y:koardinat);
{procedura vvoda koardinat tochek}
var
 i:byte;
 fin:text;
begin
 assign(fin,'L15_IN.txt');
 reset(fin);
 for i:=1 to n do
 begin
  read(fin,x[i]);
 end;
 readln(fin);
 for i:=1 to n do
 begin
  read(fin,y[i]);
 end;
 close(fin);
end;

procedure VivodKoardinat (n:integer; x,y:koardinat);
{procedura vivoda koardinat tochek}
var
 i:byte;
 fout:text;
begin
 assign(fout,'L15_23_OUT.txt');
 rewrite(fout);
 for i:=1 to n do
 begin
  write(fout,x[i]2,' ');
 end;
 writeln(fout);
 for i:=1 to n do
 begin
  write(fout,y[i]2,' ');
 end;
 close(fout);
end;

procedure sortirovka(var x,y:koardinat; n:integer);
{procedura sortirovki koardinat tochek v poryadke neubivaniya x-vih
koardinat, esli x odinakovi, to v poryadke neubivaniya y-vih koardinat,
ispol'zuem lineinuyu sortirovku po nevozrastaniyu}
var
 i,j:byte;
 buf,buf1,buf2:real;
begin
 for i:=1 to n-1 do
 for j:=i+1 to n do
 begin
  if x[i]<x[j] then
  begin
   buf:=x[i];
   x[i]:=x[j];
   x[j]:=buf;
   buf1:=y[i];
   y[i]:=y[j];
   y[j]:=buf1;
  end;
  if (x[i]=x[j]) and (y[i]<y[j]) then
  begin
   buf2:=y[i];
   y[i]:=y[j];
   y[j]:=buf2;
  end;
 end;
end;

procedure srednyaya_tochka(var x0,y0:real; var k:integer; x,y:koardinat;n:integer);
{pricedura nahogdeniya koardinati srednei tochki}
begin
 k:=n div 2+1;
 x0:=x[k];
 y0:=y[k];
end;

procedure tochki(var x1,x2,y1:real; x,y:koardinat; n,k:integer; x0,y0:real);
{procedira nahogdeniya dopolnitelnih tochek}
var
 i,j,l:integer;
begin
 i:=k;
 if x[i-1]<>x0 then {nahodim x1}
  x1:=x0-1
 else
 begin
  while x[i]=x0 do
  i:=i-1;
  if i=0 then
   x1:=x0-1
  else
   x1:=x[i];
 end;
 j:=k;            {nahodim x2}
 if x[j+1]<>x0 then
  x2:=x0+1
 else
 begin
  while x[i]=x0 do
  i:=i+1;
  if i=n+1 then
   x2:=x0+1
  else
   x2:=x[i];
 end;
{nahodim y1}
 l:=k;
 if x[l-1]<>x0 then
  y1:=y0-1
 else
  y1:=y[l-1];
end;


procedure MinMaxY (var maxy,miny:real; y:koardinat; n:integer);
{procedura nahogdeniya min i max y koardinati}
var
 i:integer;
begin
 maxy:=y[1];
 miny:=y[1];
 for i:=1 to n do
 begin
  if y[i]>maxy then
   maxy:=y[i]
  else
  if y[i]<miny then
   miny:=y[i];
 end;
end;

procedure uravnenie_pryamoi(x1,x2,y1,x0,y0,miny,maxy:real);
{nahogdenie uravneniya pryamoi i vivod ego v fail}
var
 z,a,b,m1,m2,l1,l2:real;
 fout:text;
begin
 a:=x0-x1;
 b:=x2-x0;
 if a<=b then
  z:=a
 else
  z:=b;
 m1:=x0;
 l1:=(y0+y1)/2;
 m2:=x0+z/2;
 l2:=y0-maxy+miny;
 assign (fout,'L15_23_OUT.txt');
 append (fout);
 writeln(fout,' ');
 writeln(fout,'Uravnenie pryamoi zadannoe dvumya tochkami');
 writeln (fout,'x-',m1:2:0,'/',m2:2:0,'-',m1:2:0,'= y-',l1:2:0,'/',l2:2:0,'-',l1:2:0);
 close(fout);
end;

begin
 writeln ('vvedite n - chetnoe kolichestvo tochek');
 repeat
  readln(n);
 until n mod 2=0;
 x1:=0;x2:=0;y1:=0;miny:=0;maxy:=0;k:=0;
 VvodKoardinat (n,x,y);
 Sortirovka(x,y,n);
 VivodKoardinat (n,x,y);
 srednyaya_tochka(x0,y0,k,x,y,n);
 tochki(x1,x2,y1,x,y,n,k,x0,y0);
 MinMaxY (maxy,miny,y,n);
 uravnenie_pryamoi(x1,x2,y1,x0,y0,miny,maxy);
end.