0 / 0 / 0
Регистрация: 12.01.2015
Сообщений: 7
1

Найти две наиболее удаленные друга от друга точки в заданном множестве точек

23.01.2015, 00:47. Показов 9663. Ответов 8
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Координаты n точек на плоскости заданы в виде двумерного массива K[l..n,1..2]. Найти номера двух точек, расстояние между которыми наибольшее. Вычисление расстояния между двумя точками организовать в подпрограмме.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
23.01.2015, 00:47
Ответы с готовыми решениями:

В случайном множестве точек соединить прямой линией две наиболее удаленные друг от друга
Поисковая система показала мне одну программу, решающую нечто подобное. Я был удивлён. Судя по...

Найти две наиболее удаленные друг от друга точки
Здравствуйте, пытаюсь реализовать проект для работы с 3D объектами, у меня есть матрица, с которой...

Найти две наиболее удаленные друг от друга точки
Товарищи-господа, помогите, пожалуйста, абсолютному "чайнику"! Есть задача: "Дано множество точек...

Множество точек задано на плоскости; найти две наиболее удаленных друг от друга точки
Помогите, пожалуйста, написать программу на С++, используя структуру point для хранения координат...

8
11 / 11 / 11
Регистрация: 09.12.2014
Сообщений: 89
23.01.2015, 17:42 2
Смысл программы прост:
1. Находим максимально удаленную точку, это будет первая точка
2. от этой точки считаем длинны отрезков к другим и находим самый длинный отрезок
3 к какой точке отрезок будет самым длинным то эта точка будет второй!

Вычисление длинны отрезков сам засунь в подпрограмму, мне уже некогда...

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
#include <stdio.h>
#include <math.h>
main (){
int i=0,j=0,n,first_point,second_point;
float x,y,max=0,L=0;
scanf ("%d",&n);     
float K[n][2];// n-кол во строк (точек), 2 - кол во столбцов (1 столб-координата x, 2 столб-координата y)
while (i<n){
      scanf ("%f %f",&K[i][0],&K[i][1]);
      i++;
      }
//выводим точки на экран
i=0;
while (i<n){
      printf ("point %d (%f,%f)\n",i,K[i][0],K[i][1]);
      i++;
      }
//
 
// находим наиболее удаленную точку
i=0;
while (i<n){
      while (j<2){
            if (fabs(K[i][j])>=fabs(max)) {max=fabs(K[i][j]);first_point=i;}
            j++;
            }
            j=0;
      i++;
      }
      x=K[first_point][0];
      y=K[first_point][1];
//находим максимальную длинну отрезка от этой точки до остальных
i=0;
while (i<n){
      if (L<sqrt(powf(x-K[i][0],2)+powf(y-K[i][1],2))) {L=sqrt(powf(x-K[i][0],2)+powf(y-K[i][1],2)); second_point=i;}
      i++;
      }
//
printf ("first_point=%d,second_point=%d",first_point,second_point);// выводим индексы точек
getchar ();getchar ();
}
1
2662 / 2237 / 240
Регистрация: 03.07.2012
Сообщений: 8,138
Записей в блоге: 1
24.01.2015, 12:41 3
Фигня, а не алгоритм. Что он посчитает для точек (0,8), (8,0), (9,9) ?
0
Эксперт PHP
3106 / 2591 / 1219
Регистрация: 14.05.2014
Сообщений: 7,236
Записей в блоге: 1
24.01.2015, 12:53 4
Цитата Сообщение от AlexM24 Посмотреть сообщение
Находим максимально удаленную точку, это будет первая точка
Откуда такая уверенность?

Добавлено через 5 минут
Цитата Сообщение от AlexM24 Посмотреть сообщение
C++
1
2
scanf ("%d",&n);
float K[n][2];
такая штука только в GNU-компиляторах прокатит, и то не факт. Размер массива должен быть известен во время компиляции.
0
11 / 11 / 11
Регистрация: 09.12.2014
Сообщений: 89
24.01.2015, 14:04 5
Отвечаю сразу на оба предыдущих поста. См.скрин.
Найти две наиболее удаленные друга от друга точки в заданном множестве точек

Из скрина видно, что из точек (0,8) (8,0) (9,9) в качестве 1 точки будет (9,9) а вторая (поскольку точки равноудалены от первой) будет первая из введенных в Вашем примере.
И как тоже видно из скрина программа нормально компилится под виндой.
0
2662 / 2237 / 240
Регистрация: 03.07.2012
Сообщений: 8,138
Записей в блоге: 1
24.01.2015, 14:14 6
Цитата Сообщение от AlexM24 Посмотреть сообщение
в качестве 1 точки будет (9,9)
А максимальное расстояние на самом деле между (0,8) и (8,0) и точка (9,9) не при чем
0
11 / 11 / 11
Регистрация: 09.12.2014
Сообщений: 89
24.01.2015, 14:20 7
zer0mail - Молодец! Тогда остается перебирать все расстояния от всех точек!
0
30 / 30 / 38
Регистрация: 23.01.2015
Сообщений: 174
24.01.2015, 14:53 8
А вот так пробовали ?!?!:
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
#include <stdio.h>
#include <conio.h>
#include <math.h>
 
#define N 5
 
double distance(int x1, int y1, int x2, int y2)
{
    return sqrt(pow((double)abs(x1 - x2), 2) + pow((double)abs(y1 - y2), 2));
}
 
int main(int argc, char* argv[])
{
    int M[N][2] = { { 3, 2 },
                    { 6, 4 },
                    { 1, 3 },
                    { 9, 1 },
                    { 7, 6 } };
 
    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(M[i][0], M[i][1], M[j][0], M[j][1]);
            if (d > max_dist || max_dist == 0.00)
            {
                max_dist = d;
                max_i = i; max_j = j;
            }
        }
 
    printf("(%d,%d) <--> (%d,%d) distance = %lf\n", 
        M[max_i][0],M[max_i][1], M[max_j][0], M[max_j][1], max_dist);
 
    _getch();
 
    return 0;
}
http://codepad.org/utket4Jd
Миниатюры
Найти две наиболее удаленные друга от друга точки в заданном множестве точек  
1
11 / 11 / 11
Регистрация: 09.12.2014
Сообщений: 89
27.01.2015, 14:06 9
Нашел сайт от всех проблем! Ваш алгоритм по этой ссылке
http://e-maxx.ru/algo/nearest_points
0
27.01.2015, 14:06
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
27.01.2015, 14:06
Помогаю со студенческими работами здесь

В заданном множестве точек найти три пары самых удаленных друг от друга точек
Координаты точки на площади задаются парой действительных чисел. Дано натуральное число n и...

Наиболее удаленные точки друг от друга
Координаты n точек на плоскости заданы в виде двумерного массива K. Найти номера двух точек,...

Найти две наиболее удаленных друг от друга точки
Структуры: I. Решить задачу, используя структуру point для хранения координат точки: Множество...

Найти наименее удаленные друг от друга точки на плоскости
Приветствую ребята! Нужна помощь, помогите решить задачу на С++, Заранее благодарен. В файле...


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru