Версия для печати темы
Нажмите сюда для просмотра этой темы в обычном формате
Форум «Всё о Паскале» _ Задачи _ задача про треугольник
Автор: krasnblj 11.12.2007 23:02
для всех задач дано N точек плоскости.Найти три точки среди заданых точек чтобы треугольник с вершинами в этих точках содержал бы наименьшую медиану.
ну хоть малейшие подсказки,сам код не начинал.. хотябы связь..
Автор: Lapp 12.12.2007 6:46
Ничего в голову не приходит, кроме полного перебора всех треугольников с вычислением всех трех медиан...
Задачу можно сделать более интересной, если постараться избежать повторов.
Автор: Michael_Rybak 12.12.2007 7:20
Вообще, конечно, можно тут диаграммы Вороного заюзать. Тогда получится за n^2 * log n. Рассказать?
Автор: krasnblj 14.12.2007 14:49
Michael_Rybak я этого еще не проходил,расскажи ))
Автор: Michael_Rybak 14.12.2007 19:10
можно для каждой пары вершин находить середину соединяющего их отрезка, и для этой середины сразу выбирать ближайшую вершину среди остальных (она и будет третьей).
чтобы это делать, нужно сначала построить диаграмму Вороного для этого множества точек. Тогда поиск ближайшей будет всегда происходить за log n.
Автор: krasnblj 18.12.2007 21:21
оу,не,решил делать перебором,не знаю как подойти,что за что обозначить и как выводить ответ - корродинаты начал и конца медианы или её длину?? о.О 
Автор: Michael_Rybak 19.12.2007 2:42
Ответом будут сами точки - вершины треугольника. Т.е. ты перебираешь все тройки А, В, С, для каждой тройки находишь три медианы, выбираешь наименьшую, и запоминаешь ту тройку, в которой самая маленькая наименьшая медиана. Можешь кроме треугольника вывести и ее длину.
Автор: krasnblj 6.01.2008 18:17
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)" присутствует всегда..
помгие плззззз
Автор: Michael_Rybak 6.01.2008 18:31
ну добавь проверку, что точки IJK не лежат на одной прямой.
Автор: krasnblj 6.01.2008 21:54
так если 2 точки лежат на одной прямой,а третья где-то в стороне,то тогда тругольник может существовать!!
Автор: Michael_Rybak 6.01.2008 21:59
проверяй что все три не лежат. любые две всегда лежат
Автор: krasnblj 6.01.2008 22:07
хм,не предтваляю как это написать.. 
Автор: Michael_Rybak 6.01.2008 22:35
Точки А В С лежат на одной прямой если (AX-BX)(CY-BY) = (CX-BX)(AY-BY)
Автор: krasnblj 7.01.2008 19:45
спс,но мне другой способ подсказали,ищу как его внедрить )))
Автор: krasnblj 8.01.2008 2:29
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 выводит равный нулю????
Автор: Michael_Rybak 8.01.2008 6:50
Потому что нужно не m[3]:=mq; а mq:=m[3];
Автор: krasnblj 8.01.2008 15:56
щёрт,точно,ты и не представляешь как я тебя абажаю ))))))))) 
Автор: Michael_Rybak 8.01.2008 16:08