Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/10: Рейтинг темы: голосов - 10, средняя оценка - 4.60
kalinkinan
0 / 0 / 0
Регистрация: 12.01.2015
Сообщений: 7
1

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

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

Координаты n точек на плоскости заданы в виде двумерного массива K[l..n,1..2]. Найти номера двух точек, расстояние между которыми наибольшее. Вычисление расстояния между двумя точками организовать в подпрограмме.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.01.2015, 00:47
Ответы с готовыми решениями:

Реализавать функцию поиска двух точек в массиве наиболее удаленных друг от друга
Реализавать функцию поиска двух точек в массиве наиболее удаленных друг от...

Как правильно объявить две структуры с указателями друг на друга
В одном файле определены две структуры. typedef struct Tdata1 { int a; ...

Посчитать две изменяющиеся функции которые умножаются друг на друга
Здраствуйте. Мне дали задание написать программу которая вычисляет значение...

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

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

8
AlexM24
10 / 10 / 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
zer0mail
2458 / 2094 / 217
Регистрация: 03.07.2012
Сообщений: 7,588
Записей в блоге: 1
24.01.2015, 12:41 3
Фигня, а не алгоритм. Что он посчитает для точек (0,8), (8,0), (9,9) ?
0
Kerry_Jr
Эксперт PHP
2211 / 2007 / 940
Регистрация: 14.05.2014
Сообщений: 5,869
Записей в блоге: 1
Завершенные тесты: 5
24.01.2015, 12:53 4
Цитата Сообщение от AlexM24 Посмотреть сообщение
Находим максимально удаленную точку, это будет первая точка
Откуда такая уверенность?

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

Из скрина видно, что из точек (0,8) (8,0) (9,9) в качестве 1 точки будет (9,9) а вторая (поскольку точки равноудалены от первой) будет первая из введенных в Вашем примере.
И как тоже видно из скрина программа нормально компилится под виндой.
0
zer0mail
2458 / 2094 / 217
Регистрация: 03.07.2012
Сообщений: 7,588
Записей в блоге: 1
24.01.2015, 14:14 6
Цитата Сообщение от AlexM24 Посмотреть сообщение
в качестве 1 точки будет (9,9)
А максимальное расстояние на самом деле между (0,8) и (8,0) и точка (9,9) не при чем
0
AlexM24
10 / 10 / 11
Регистрация: 09.12.2014
Сообщений: 89
24.01.2015, 14:20 7
zer0mail - Молодец! Тогда остается перебирать все расстояния от всех точек!
0
1XPLoade1
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
Миниатюры
Найти две наиболее удаленные друга от друга точки в заданном множестве точек  
AlexM24
10 / 10 / 11
Регистрация: 09.12.2014
Сообщений: 89
27.01.2015, 14:06 9
Нашел сайт от всех проблем! Ваш алгоритм по этой ссылке
http://e-maxx.ru/algo/nearest_points
0
27.01.2015, 14:06
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.01.2015, 14:06

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

Через две точки проведен отрезок прямой. Найти среди заданных трех точек такую, что также относится к этому отрезку
Собственно сама задача. Через две точки проведен отрезок прямой. Найти среди...

Даны две точки A(x,y) и В(х,у). Составить программу, определяющую, которая из точек находится ближе к началу координат
Ветвление


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru