сумма растояний

[Alex_sim]

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

int [][]mass={{10,2},{3,4},{5,6},{7,8}};
        Random r=new Random();
        int [] result = new int [3];
        int x1=0,x2=0,y1=0,y2=0,A=0,B=0,Z=0,T=0,sum=0;
                double rst=0;

        x1=mass[0][0];
        x2=mass[1][0];
        y1=mass[0][1];
        y2=mass[1][1];

        A=x2-x1;
        B=y2-y1;
        Z=A*A;
        T=B*B;
        sum=Z+T;

        rst += Math.sqrt(sum);


        x1=mass[0][0];
        x2=mass[2][0];
        y1=mass[1][0];
        y2=mass[2][1];

        A=x2-x1;
        B=y2-y1;
        Z=A*A;
        T=B*B;
        sum=Z+T;
        rst +=Math.sqrt(sum);

        x1=mass[0][0];
        x2=mass[3][0];
        y1=mass[1][0];
        y2=mass[3][1];

        A=x2-x1;
        B=y2-y1;
        Z=A*A;
        T=B*B;
        sum=Z+T;
        rst +=Math.sqrt(sum);
System.out.println(rst);

[Stilet]

Типа такого судя по твоему коду...

        
for(int i=1;i<3;i++){
        x1=mass[0][0];
        y1=mass[0][0];

        x2=mass[i][0];
        y2=mass[i][1];

        A=x2-x1;
        B=y2-y1;
        Z=A*A;
        T=B*B;
        sum=Z+T;

        rst += Math.sqrt(sum);
};

[pray_driver]

я бы предложил вариант определения расстояний такой:
(си не знаю, на пхп напишу - очень похоже на си)

<?php
$pix[1][1]=1; //  Определим точки массивом $pix
$pix[1][2]=2;

$pix[2][1]=3;
$pix[2][2]=4;

$pix[3][1]=5;
$pix[3][2]=6;

$pix[4][1]=7;
$pix[4][2]=8;

$n=count($pix); // длина массива


$rasst=1000000; // Пусть начальное расстояние очень велико


for ( $j=1; $j<=$n; $j++ ) {  //Начинаем перебор по каждой точке
    $rasst_new=0; // сначала текущее расстояние равно 0
    for  ( $k=1; $k<=$n; $k++ ) {
    // Проходимся по точкам, прибавляем расстояния до $pix[$j]
        $rasst_new += sqrt( ($pix[$j][1]-$pix[$k][1]) * ($pix[$j][1]-$pix[$k][1]) + ($pix[$j][2]-$pix[$k][2]) * ($pix[$j][2]-$pix[$k][2]) );
        }
    if ($rasst_new <= $rasst) { //Если новое расстояние меньше старого, то старое обновляем на новое
        $rasst = $rasst_new;
        $tochka = $j; //Искомая точка
    }
}
echo "(".$pix[$tochka][1].";".$pix[$tochka][2]."), rasst=".$rasst."<br>"; // Выводим ответ

?>

[Alex_sim]

Сообщение от Stilet

Типа такого судя по твоему коду...

        
for(int i=1;i<3;i++){
        x1=mass[0][0];
        y1=mass[0][0];

        x2=mass[i][0];
        y2=mass[i][1];

        A=x2-x1;
        B=y2-y1;
        Z=A*A;
        T=B*B;
        sum=Z+T;

        rst += Math.sqrt(sum);
};

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

[Stilet]

У-у-у Тут нужно описать процедуру...
В нее передавай номер точки а она уже будет сравнивать с остальными исключая эту точку.

[pray_driver]

Сообщение от Stilet

У-у-у Тут нужно описать процедуру...
В нее передавай номер точки а она уже будет сравнивать с остальными исключая эту точку.

зациклить переход от вершины к вершине и все дела. замечу, что точку можно не исключать, поскольку расстояние от неё до неё самой равно нулю, значит на общее расстояние никак не повлияет Зачем мучаться и исключать?

[pray_driver]

Кстати, гораздо интереснее задача была бы найти на всей плоскости точку, сумма растояний от которой до множества точек была бы минимальной. То есть не среди перечисленных, а неизвестную точку (x;y). Например для отрезка - это была бы середина отрезка Для треугольника - центр масс помоему. а для произвольного набора точек попробуй поищи )))

[Alex_sim]

а ты можешь в коде показать как сравнивать координаты точек а то я совсем запутался??

[pray_driver]

Alex_sim, если это вопрос ко мне, то я честно немножко не понимаю с какой целью и по каким параметрам её сравнивать. Я там выше написал алгоритм - находит среди точек ту, сумму расстояний от которой до других минимальна. Могу его по русски описать так:

задать глобальное_расстояние = 10e37 (очень большое))));
По всем i от 1 точки до последней делать:
    текущее_расстояние := 0 (минимальное);
    По всем j от 1 точки до последней делать:
        текущее_расстояние прибавить расстояние от i до j;
    Если текущее_расстояние меньше глобального_расстояния, то запомнить точку i;

- он пройдется по всем точкам, для каждой точки пройдет ещё по всем точкам. Где расстояние минимально - эту точку запомнит (последняя запомненная i). Вот её и выводить

Трудоёмкость такого конечно n^2 не слишком оптимизировано. Полный перебор, зато всё находит

[evg_m]

mX:=(x[1]+x[2]+...+x[n])/N
mY=([Y[1]+y[2]+..+y[n])/N
//средняя точка (центр тяжести) множества точек
L[1]:=(MX-X[1])^2 +(My-Y[1])^2
L[2]:=(MX-X[2])^2 +(My-Y[2])^2
...
L[N]:=(MX-X[N])^2 +(My-Y[N])^2
//расстояния от центра до всех точек
min(L[1],L[2],...,L[N])
//точка самая близкая к центру