Перебор между собой всех строк матрицы

180

25 мая 2022, 00:50

У меня вот такая вот задача:

В файле записано количество точек на плоскости и их координаты. Поместить эти координаты в двумерный динамический массив. Найти две точки, находящиеся на максимальном удалении друг от друга. Расстояние R между точками с координатами (x1, y1) и (x2, y2) вычисляется по формуле: R=sqrt((x2-x1)^2+(y2-y1)^2). На экран вывести координаты этих точек и расстояние между ними.

Пока, единственная мысль у меня, это создать массив всех вариаций расстояний и потом из него искать максимальное, но у меня возникли проблемы с созданием этого массива. А точнее, каким именно образом перебрать все точки?

если что, данные в файле (и соответственно двумерный массив) выглядит следующим образом:

1.1 1.2
3.2 3.2
2.2 4.5 
и тд...

Если это поможет, могу приложить код с формированием данного массива.

Answer 1

Тема не актуальна, решила. Но вдруг кому пригодится.

double distance(int x1, int y1, int x2, int y2){
    return sqrt(pow((double)abs(x1 - x2), 2) + pow((double)abs(y1 - y2), 2));
}

//dots - матрица с точками размером [количество точек][2]
//distance-функция с формулой нахождения расстояния, выше написала
double max_dist = 0.00;
int max_i = 0, max_j = max_i;
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++){
        double d = distance(dots[i][0], dots[i][1], dots[j][0], dots[j][1]);
        if (d > max_dist || max_dist == 0.00){
            max_dist = d;
            max_i = i; max_j = j;
        }
    }

Answer 2

Оптимизацию предлагаю. Как можно меньше нужно вычислять квадратные корни и умножения. Храним также max_distance_x , max_distance_y.

Если distance_x < max_distance_x И distance_y < max_distance_y значит дистанция будут меньше без умножений и корней. И если distance_x > max_distance_x И distance_y > max_distance_y то больше.

//dots - матрица с точками размером [количество точек][2]
//distance-функция с формулой нахождения расстояния, выше написала
double max_dist2 = 0.00;
double max_dist_x = 0.00;
double max_dist_y = 0.00;
int max_i = 0, max_j = max_i;
for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n; j++) {
      double dx = abs(dots[i][0] - dots[j][0]);
      double dy = abs(dots[i][1] - dots[j][1]);
      if ( dx > max_dist_x || dy > max_dist_y ) {
         double d2 = dx*dx+dy*dy ;
         if ( d2 > max_dist2 ) {
           max_dist2 = d2 ;
           max_dist_x = dx ;
           max_dist_y = dy ;
           max_i = i; max_j = j; } } } }
// максимальное расстояние = sqrt(max_dist2)