Помогите пожалуйста!! Завтра сдавать, я в графах ни бум-бум...очень прошу!
23. На плоскости заданы 2n точек своими координатами. Найдите уравнение какой-либо прямой, делящей данное множество точек на два подмножества по n точек.
Условие не совсем понятно.А что если некоторые точки будут лежать на искомой прямой,то к какому подмножеству они буду относиться?Как можно задачать координаты точек?(целые или вещественные числа?)И самое главное,как множество точек,которые как таковой между собой никак не связаны, относится к графам?Если есть какие то конретные предписания,как это делать,то желательно о них упомянуть.И в каком виде нужно найти уравнение прямой?Можно например, как функцию у от х ,можно как точку и угол наклона.....
у меня только это условие и никаких пояснений( задача относиться к теме комбинаторные алгоритмы и алгоритмы на графах, которую я совсем не пониманию..
ммм, попробую завтра утром сделать, если успею, ночью голова не варит совсем, спасибо большое вам..
не понимаю как вот это реализовать
4. найти минимальный ненулевой угол, опирающийся на точки из данного множества (назовем его A);
5. произвести поворот системы координат на A/2 (вокруг произвольной точки).
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;
a:= Random*Pi;
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], потому что его тангенс наклона вдвое превышает все возможные тангенсы наклона отрезков, соединяющих точки из набора.
правка: увеличил буквы в уравнении прямой, а то тавтология
добрый вечер, снова возвращаюсь к этой программе, которую я так и не сдала. Большое спасибо, за предложенные алгоритмы Lapp и TarasBer, хотела бы разобраться в вашем варианте TarasBer. Я так понимаю последовательность действий такая:
1. записываем координаты точек в массивы X и Y
2. далее нужно найти прямую,
a[i]a[j]-это 2 точки нашего исходного массива,принципи это то, что нужно чтобы задать любую прямую на плоскости(пространстве))Но так же учтите,что решение TarasBer не универсально.
Я думаю, что в условии должно быть требование, что никакие две точки не слвпадают, иначе задача просто нерешаема.
a[i] и a[j] - две точки.
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] - так значит вот этот пункт верный?
нашла на просторах интернета похожую задачу на мою среди олимпиадных задач, к ней был приложен алгоритм решения, довольно подробно расписанный что и к чему, сейчас его пробую реализовать и вроде получается, не знаю, разрешено ли в форуме давать ссылки на другие сайты(( если можно, то я скину ссылочку, кому интересно..
Вы можете взять и скопировать этот алгоритм суда,если хотите,и да,здесь можно давать ссылки на сторонние ресурсы,по крайней мере,админы переодически помогают,давая ссылки на нужную информацию с сторонних ресурсов.
Отсортировав координаты точек в порядке неубывания Х-овых координат, а в случае одинаковых Х-овых координат в порядке неубывания У-овых координат, находим координаты средней точки (находящуюся в позиции 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).
кстати я всё сделала по этому алгоритму, всё работает) но уверенности в том что правильно нету, не согласитесь его посмотреть))?
Ну чтобы проверить,правильно или нет,нарисуйте на бумажке пару примеров, вбейте в вашу программу и посмотрите результаты ,которые вы получили,и сравните с вашими результатами.Во вторых,выложите код того, как вы это реализовали,люди не телепаты, может быть вы доработали алгоритм под вашу задачу,а может и нет,а если и изменили,то как.
Чем отличается алгоритм от нужной вам задачи.
вот код:
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.