Технический форум

Технический форум (http://www.tehnari.ru/)
-   C/C++/С# (http://www.tehnari.ru/f42/)
-   -   Расстояние между точками (http://www.tehnari.ru/f42/t106418/)

Alex1895 17.01.2016 17:30

Расстояние между точками
 
Даны два массива вещественных чисел, x и y. Их длина одинакова и равна n. Каждый (i-й) элемент массива x содержит абсциссу некоторой точки ri на плоскости, а элемент массива y - её ординату. Найти пару точек, расстояние между которыми минимально ( если таких пар несколько, можно выбрать любую). Напечатать номера точек и расстояние между ними.
Помогите пожалуйста решить задачу, на языке С++.

nikniknik2016 02.03.2016 23:00

Код:

//для std::cout
#include <iostream>

//математические функции
#include <cmath>

//для NaN (переменная без значения)
#include <limits>

using namespace std;

namespace {

//исходные массивы данных (количество элементов в обоих должно совпадать)
const float x_coords[] = { 1,2,2,4,10 }; //координаты по оси X
const float y_coords[] = { 1,2,4,4,20 }; //координаты по оси Y

//определяем NaN
const float NaN = numeric_limits<float>::quiet_NaN();

//структура данных для хранения координат точки
struct Point
{
  float x;
  float y;
  Point(float x = NaN, float y = NaN) : x(x), y(y) {}

  //передача данных точки в поток вывода
  void to_std_cout() {
    std::cout << x << ',' << y;
  }
};

//получить неотрицательное значение
float abs_float(float f) {
    return f >= 0 ? f : -f;
}

//рассчет расстояния между точками
float calc_distance(const Point& a, const Point& b)
{
  /*
    рассчет расстояния осуществляется с помощью свойств прямоугольного треугольника,
    а точнее - квадрат гипотенузы равен сумме квадратов катетов
  */
  const float k0 = abs_float(a.x - b.x); //первый катет
  const float k1 = abs_float(a.y - b.y); //второй катет

  const float g2 = pow(k0, 2) + pow(k1, 2); //квадрат гипотенузы
  return sqrt(g2); //извлекаем квадратный корень и получаем расстояние между точками
}

void process()
{
  //здесь хранятся минимальное расстояние и точки, для которых это расстояние найдено
  Point min_a;
  Point min_b;
  float min_distance = NaN; //сначала минимальное расстояние не имеет значения
  /*
    определяем количество заданных точек
    для этого узнаем размер в байтах всего массива x_coords и делим на размер элемента в байтах
    если бы x_coords был передан в качестве указателя, то такой способ бы не подошел
  */
  const unsigned cnt_of_points = sizeof(x_coords) / sizeof(x_coords[0]);

  //запустим цикл для всех заданных точек
  for(unsigned i = 0; i < cnt_of_points; ++i)
  {
      /*
        i - индекс первой точки в паре
        j - индекс второй точки в паре
        вторую точку надо искать только из последующих точек (начиная с j = i + 1),
        т.к. предыдущие точки уже были рассчитаны
      */
      for(unsigned j = i + 1; j < cnt_of_points; ++j)
      {
        const Point a(x_coords[i], y_coords[i]); //первая точка
        const Point b(x_coords[j], y_coords[j]); //вторая точка
        const float distance = calc_distance(a, b); //расстояние между точками

        /*
          если минимальное расстояние не имеет значеня
          или
          текущее расстояние меньше минимального,
          то запоминаем текущее расстояние как минимальное,
          также запоминаем текущие точки
        */
        if(isnan(min_distance) || distance < min_distance)
        {
            min_distance = distance;
            min_a = a;
            min_b = b;
        }
      }
  }

  //отдаем полученную информацию на устройство вывода (консоль, например)
  std::cout << "min distance: " << min_distance << endl;
  std::cout << "point A: ";
  min_a.to_std_cout();
  std::cout << endl;
  std::cout << "point B: ";
  min_b.to_std_cout();
  std::cout << endl;
}

} //namespace

int main()
{
    process();
    return 0;
}


nikniknik2016 02.03.2016 23:06

Здесь, правда, печатаются не номера точек, а их координаты

Вот код функции process, где еще печатаются номера точек:

Код:

void process()
{
  //здесь хранятся минимальное расстояние и точки, для которых это расстояние найдено
  Point min_a;
  Point min_b;
  float min_distance = NaN; //сначала минимальное расстояние не имеет значения
  unsigned min_i = -1;
  unsigned min_j = -1;
  /*
    определяем количество заданных точек
    для этого узнаем размер в байтах всего массива x_coords и делим на размер элемента в байтах
    если бы x_coords был передан в качестве указателя, то такой способ бы не подошел
  */
  const unsigned cnt_of_points = sizeof(x_coords) / sizeof(x_coords[0]);

  //запустим цикл для всех заданных точек
  for(unsigned i = 0; i < cnt_of_points; ++i)
  {
      /*
        i - индекс первой точки в паре
        j - индекс второй точки в паре
        вторую точку надо искать только из последующих точек (начиная с j = i + 1),
        т.к. предыдущие точки уже были рассчитаны
      */
      for(unsigned j = i + 1; j < cnt_of_points; ++j)
      {
        const Point a(x_coords[i], y_coords[i]); //первая точка
        const Point b(x_coords[j], y_coords[j]); //вторая точка
        const float distance = calc_distance(a, b); //расстояние между точками

        /*
          если минимальное расстояние не имеет значеня
          или
          текущее расстояние меньше минимального,
          то запоминаем текущее расстояние как минимальное,
          также запоминаем текущие точки
        */
        if(isnan(min_distance) || distance < min_distance)
        {
            min_distance = distance;
            min_a = a;
            min_b = b;
            min_i = i;
            min_j = j;
        }
      }
  }

  //отдаем полученную информацию на устройство вывода (консоль, например)
  std::cout << "min distance: " << min_distance << endl;
  std::cout << "point A: [" << min_i << "] ";
  min_a.to_std_cout();
  std::cout << endl;
  std::cout << "point B: [" << min_j << "] ";
  min_b.to_std_cout();
  std::cout << endl;
}



Часовой пояс GMT +4, время: 04:32.

Powered by vBulletin® Version 4.5.3
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.