Форум программистов, компьютерный форум CyberForum.ru

Найти две наиболее удаленных друг от друга точки - C++

Восстановить пароль Регистрация
 
Обормот
0 / 0 / 0
Регистрация: 24.06.2014
Сообщений: 14
25.06.2014, 20:03     Найти две наиболее удаленных друг от друга точки #1
Структуры:
I. Решить задачу, используя структуру point для хранения координат точки:
Множество точек задано в пространстве. Найти две наиболее удаленных друг от друга точки.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.06.2014, 20:03     Найти две наиболее удаленных друг от друга точки
Посмотрите здесь:

Разработать программу для нахождения пары самых удаленных друг от друга точек C++
найти две наиболее удаленных друг от друга точки (множество точек задано на плоскости) C++
C++ Найти номера наиболее и наименее удаленных друг от друга точек
C++ Задан массив точек. Найти номера наиболее и наименее удаленных друг от друга точек.
C++ Динамическая матрица (Найти координаты двух точек, наиболее удалённых друг от друга)
C++ Определить бъют ли две фигуры на шахматной доске друг друга
Найти наименее удаленные друг от друга точки на плоскости C++
Найти номера двух наиболее удаленных точек C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
27.06.2014, 18:59     Найти две наиболее удаленных друг от друга точки #2
гугл: диаметр множества. Простым перебором (с предварительной генерацией точек):
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**
I. Решить задачу, используя структуру point для хранения координат точки:
Множество точек задано в пространстве. Найти две наиболее удаленных друг
от друга точки.
**/
#include<cstdio>
#include<vector>
#include<cmath>
#include<random>
struct Point {
    double x;
    double y;
};
 
double distance(const Point& rhs, const Point& lhs) {
//вычисляет расстояние между заданными точками.
    return sqrt(
               pow(rhs.x - lhs.x, 2)
               + pow(rhs.y - lhs.y, 2)
           );
}
 
void generate(std::vector<Point>& v) {
//забивает случайными значениями.
    std::random_device rd;
    std::uniform_real_distribution<double> spread (-1.0,1.0);
    for (auto& w : v) {
        w.x = spread(rd);
        w.y = spread(rd);
    }
}
 
std::pair<Point, Point> find_diameter( const std::vector<Point>& v) {
//вычисляет расстояние для каждой пары точек, возвращает
//максимальное. O(n^2); v.size() >= 2 !
 
    double max = 0;
    std::pair<Point , Point> maxpair; // для сохранения лучшей пары точек
 
    for ( auto it = v.begin(); it != v.end(); ++it) {
        for (auto inner = it + 1; inner < v.end(); ++inner) {
            auto tmp = distance( *it, *inner );
            if (max < tmp) {
                //найдена новая лучшая пара.
                maxpair.first = *it;
                maxpair.second = *inner;
                max = tmp;
            }
        }
    }
    return maxpair;
}
 
 
int main() {
    auto size = 1000;
    std::vector<Point> universe(size);
    generate(universe);
 
    auto result_points = find_diameter(universe);
    printf("Диаметр множества: %f\nнайден на точках (%f, %f) и (%f, %f)\n",
           distance(result_points.first, result_points.second),
           result_points.first.x, result_points.first.y,
           result_points.second.x, result_points.second.y
          );
    return 0;
}
Yandex
Объявления
27.06.2014, 18:59     Найти две наиболее удаленных друг от друга точки
Ответ Создать тему
Опции темы

Текущее время: 10:21. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru