задача про треугольник, и его медиану.. Опции

[krasnblj]

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

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

[Lapp]

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

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

[Michael_Rybak]

Вообще, конечно, можно тут диаграммы Вороного заюзать. Тогда получится за n^2 * log n. Рассказать?

[krasnblj]

Michael_Rybak я этого еще не проходил,расскажи ))

[Michael_Rybak]

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

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

[krasnblj]

оу,не,решил делать перебором,не знаю как подойти,что за что обозначить и как выводить ответ - корродинаты начал и конца медианы или её длину?? о.О

[Michael_Rybak]

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

[krasnblj]

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]

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

[krasnblj]

так если 2 точки лежат на одной прямой,а третья где-то в стороне,то тогда тругольник может существовать!!

[Michael_Rybak]

проверяй что все три не лежат. любые две всегда лежат

[krasnblj]

хм,не предтваляю как это написать..

[Michael_Rybak]

Точки А В С лежат на одной прямой если (AX-BX)(CY-BY) = (CX-BX)(AY-BY)

[krasnblj]

спс,но мне другой способ подсказали,ищу как его внедрить )))

[krasnblj]

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]

Потому что нужно не m[3]:=mq; а mq:=m[3];

[krasnblj]

щёрт,точно,ты и не представляешь как я тебя абажаю )))))))))

[Michael_Rybak]