IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> задача про треугольник, и его медиану..
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Мужской

Репутация: -  0  +


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

ну хоть малейшие подсказки,сам код не начинал.. хотябы связь..
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Ничего в голову не приходит, кроме полного перебора всех треугольников с вычислением всех трех медиан...

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Вообще, конечно, можно тут диаграммы Вороного заюзать. Тогда получится за n^2 * log n. Рассказать?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Мужской

Репутация: -  0  +


Michael_Rybak я этого еще не проходил,расскажи ))
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

чтобы это делать, нужно сначала построить диаграмму Вороного для этого множества точек. Тогда поиск ближайшей будет всегда происходить за log n.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Мужской

Репутация: -  0  +


оу,не,решил делать перебором,не знаю как подойти,что за что обозначить и как выводить ответ - корродинаты начал и конца медианы или её длину?? о.О mega_chok.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Ответом будут сами точки - вершины треугольника. Т.е. ты перебираешь все тройки А, В, С, для каждой тройки находишь три медианы, выбираешь наименьшую, и запоминаешь ту тройку, в которой самая маленькая наименьшая медиана. Можешь кроме треугольника вывести и ее длину.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Мужской

Репутация: -  0  +



PROGRAM minmed;

VAR N,I,J,K:INTEGER;
X:ARRAY [1..100] OF REAL;
Y:ARRAY [1..100] OF REAL;
mdd,R1,R2,R3,m1,m2,m3,med,Lx,Ly,Px,Py,Mx,My,Ax,Ay,Bx,By,Cx,Cy:REAL;
TR:BOOLEAN;

BEGIN
WRITELN ('нахождение треугольника с минимальной медианой');

REPEAT
WRITE ('ведите число точек = ');
READLN (N);
IF ((N<3) OR (N>100)) THEN
WRITELN ('неверное число точек');
UNTIL ((N>=3) AND (N<=100));
FOR I:=1 TO N DO
BEGIN
WRITELN ('введите координаты ',I,' точки');
WRITE ('ведите абсциссу = ');

READLN (X[I]);
WRITE ('введите ординату = ');
READLN (Y[I]);
END;

mdd:=32767;
TR:=FALSE;
FOR I:=1 TO N-2 DO
BEGIN
FOR J:=I+1 TO N-1 DO
BEGIN
FOR K:=J+1 TO N DO
BEGIN
R1:=SQRT(SQR(X[J]-X[I])+SQR(Y[J]-Y[I]));
R2:=SQRT(SQR(X[K]-X[I])+SQR(Y[K]-Y[J]));
R3:=SQRT(SQR(X[I]-X[K])+SQR(Y[I]-Y[K]));
Px:=X[I];
Py:=Y[I];
Lx:=X[J];
Ly:=Y[J];
Mx:=X[K];
My:=Y[K];
IF ((R1+R2>R3) AND (R1+R3>R2) AND (R2+R3>R1)) THEN
BEGIN
m1:=sqrt(sqr(((x[j]+x[k])/2)-X[i])+sqr(((y[j]+y[k])/2)-Y[I]));
m2:=sqrt(sqr(((x[i]+x[k])/2)-X[j])+sqr(((y[i]+y[k])/2)-Y[j]));
m3:=sqrt(sqr(((x[j]+x[i])/2)-X[k])+sqr(((y[j]+y[i])/2)-Y[k]));
med:=m1;
IF m2<med THEN
Med:=m2;
IF m3<med THEN
Med:=m3;
IF (med<mdd) THEN
BEGIN
mdd:=med;
Ax:=X[I];
Ay:=Y[I];
Bx:=X[J];
By:=Y[J];
Cx:=X[K];
Cy:=Y[K];
END;
TR:=TRUE;
END;
END;
END;
END;

IF (TR=TRUE) THEN
BEGIN
WRITELN ('тругольник с наименьшей медианой лежит на точках:');
WRITELN ('TR1=(',Ax,';',Ay,'), TR2=(',Bx,';',By,'), TR3=(',Cx,';',Cy,')');
END
ELSE
WRITELN ('невозможно построить треугольник');
END.



в ощем написал код,всё работает,но такой тест:

количество точек
: 5

точки:

(1,1)
(-1,-1)
(0,0)
(0.5,0.5)
(-0.5,-0.5)

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

зы: когда мы вводим точки в другом поряд выводит другой ответ,хотя точка "(-0.5,-0.5)" присутствует всегда..

помгие плззззз smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


ну добавь проверку, что точки IJK не лежат на одной прямой.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Мужской

Репутация: -  0  +


так если 2 точки лежат на одной прямой,а третья где-то в стороне,то тогда тругольник может существовать!!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


проверяй что все три не лежат. любые две всегда лежат smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Мужской

Репутация: -  0  +


хм,не предтваляю как это написать.. blink.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Точки А В С лежат на одной прямой если (AX-BX)(CY-BY) = (CX-BX)(AY-BY)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Мужской

Репутация: -  0  +


спс,но мне другой способ подсказали,ищу как его внедрить )))
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Мужской

Репутация: -  0  +



PROGRAM minmed;

VAR N,I,J, K:INTEGER;
X,Y:ARRAY [0..100] OF REAL;
mq:REAL;
tk:BOOLEAN;
R:ARRAY [1..3] OF REAL;
M:ARRAY [1..3] OF REAL;
TR:array [1..3,1..2] of real;
LABEL 14;
label 15;
label 1;
label 4;

FUNCTION DL(A,B,C,D:REAL):REAL;
BEGIN
DL:=SQRT((A-B)*(A-B)+(C-D)*(C-D))
END;

function med(a,b,c,d,e,f:real):real;
begin
med:=sqrt( sqr(((a+b)/2)-c) + sqr(((d+e)/2)-f) );
end;

BEGIN
WRITELN ('нахождение треугольника с минимальной медианой');

REPEAT
WRITE ('ведите число точек = ');
READLN (N);
IF ((N<3) OR (N>100)) THEN
WRITELN ('неверное число точек');
UNTIL ((N>=3) AND (N<=100));
FOR I:=1 TO N DO
BEGIN
REPEAT
WRITELN ('ввеите координаты ',I,' точки');
WRITE ('введите абсциссу точки = ');
READLN (X[I]);
WRITE ('введите ординату точки = ');
READLN (Y[I]);
TK:=TRUE;
FOR J:=I DOWNTO 1 DO
BEGIN
IF ((X[I]=X[J]) AND (Y[I]=Y[J]) AND (I<>J)) THEN
BEGIN
WRITELN ('точки не должны повторяться');
TK:=FALSE;
END;
END;
UNTIL (TK=TRUE);
END;

FOR I:=1 TO (N-2) DO
BEGIN
FOR J:=I+1 to (n-1) DO
BEGIN
1:FOR K:=J+1 TO N DO
BEGIN
m[1]:=med(x[j],x[k],X[i],y[j],y[k],Y[I]);
m[2]:=med(x[K],x[I],X[j],y[K],y[I],Y[j]);
m[3]:=med(x[I],x[J],X[k],y[I],y[J],Y[k]);
end;
begin
writeln (m[1]);
writeln (m[2]);
writeln (m[3]);


if ((m[3]<m[2]) and (m[3]<m[1])) then
m[3]:=mq;
if ((m[2]<m[3]) and (m[2]<m[1])) then
m[2]:=mq;
if ((m[1]<m[2]) and (m[1]<m[3])) then
m[1]:=mq;
writeln(mq);
end;
end;
end;

end.





ну поччеееееемууууу он всегда MQ выводит равный нулю????
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Потому что нужно не m[3]:=mq; а mq:=m[3];
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Мужской

Репутация: -  0  +


lol.gif щёрт,точно,ты и не представляешь как я тебя абажаю ))))))))) give_rose.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 19.09.2020 19:55
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name